一份代码,用c++编译超时,用c++17编译正常,会是什么原因?
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5, M = 3e5+5, Q = 5e5+5;
int n, log2n, m, q;
int fa[N], top[N], tot, t[N<<1];
int num[N], ak[Q];
int dfsnum, pl[N<<1], pr[N<<1], rev[N<<1], f[N<<1][22];
vector<int> e[N<<1];
pair<int, int> edge[M];
bool vis[N<<1];
vector<pair<int, int> > vec;
struct tree{
#define mid ((l+r)>>1)
#define ls (now<<1)
#define rs (now<<1|1)
pair<int, int> a[N<<2];
void up(int now){
a[now] = max(a[ls], a[rs]);
}
void build(int now, int l, int r){
if (l == r){
a[now] = make_pair(num[rev[l]], l);
return;
}
build(ls, l, mid);
build(rs, mid+1, r);
up(now);
}
void change(int now, int l, int r, int s, int k){
if (l == r){
a[now].first = k;
return;
}
if (s <= mid) change(ls, l, mid, s, k);
else change(rs, mid+1, r, s, k);
up(now);
}
pair<int, int> ask(int now, int l, int r, int s, int t){
if (s <= l && r <= t)
return a[now];
pair<int, int> res(0, 0);
if (s <= mid) res = max(ask(ls, l, mid, s, t), res);
if (t > mid) res = max(ask(rs, mid+1, r, s, t), res);
return res;
}
#undef mid
#undef ls
#undef rs
}T;
int getfa(int x){return x==fa[x]?x:fa[x]=getfa(fa[x]);}
void dfs(int u){
if (u <= n) rev[dfsnum+1] = u;
pl[u] = u<=n?++dfsnum:dfsnum+1;
for (int i = 1; i <= log2n; i++)
f[u][i] = f[f[u][i-1]][i-1];
for (int i = 0; i < e[u].size(); i++){
int v = e[u][i];
f[v][0] = u;
dfs(v);
}
pr[u] = dfsnum;
}
int main(){
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// cout << sizeof(num)+sizeof(ak)+sizeof(e)+sizeof(edge)+sizeof(f)+sizeof(fa)+sizeof(pl)+sizeof(pr)+sizeof(rev)+sizeof(t)+sizeof(top)+sizeof(vis)+sizeof(T) << endl;
cin >> n >> m >> q;
log2n = log2(n);
for (int i = 1; i <= n; i++)
cin >> num[i];
for (int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
edge[i] = make_pair(u, v);
}
for (int i = 1; i <= q; i++){
int opt;
cin >> opt;
if (opt == 1)
cin >> ak[i];
else{
int id;
cin >> id;
vis[id] = 1;
vec.push_back(make_pair(id, i));
}
}
for (int i = 1; i <= m; i++)
if (!vis[i])
vec.push_back(make_pair(i, q+1));
for (int i = 1; i <= n; i++)
fa[i] = i, top[i] = i, t[i] = q+1;
tot = n;
for (int i = vec.size()-1; i >= 0; i--){
int u = edge[vec[i].first].first, v = edge[vec[i].first].second;
u = getfa(u), v = getfa(v);
if (u == v) continue;
fa[u] = v;
e[++tot].push_back(top[u]);
e[tot].push_back(top[v]);
top[v] = tot;
t[tot] = vec[i].second;
}
memset(vis, 0, sizeof(vis));
tot++;
for (int i = 1; i <= n; i++){
int u = getfa(i);
if (!vis[top[u]]){
vis[top[u]] = 1;
e[tot].push_back(top[u]);
}
}
dfs(tot);
T.build(1, 1, n);
for (int i = 1; i <= q; i++){
if (!ak[i]) continue;
int u = ak[i], _t = i;
for (int j = log2n; j >= 0; j--)
if (t[f[u][j]] >= _t)
u = f[u][j];
pair<int, int> res = T.ask(1, 1, n, pl[u], pr[u]);
T.change(1, 1, n, res.second, 0);
cout << res.first << endl;
}
return 0;
}