题目链接：http://codeforces.com/contest/1416/problem/D
应该是图上的比较经典的问题了（然而我不会
用并查集把图区间化，思想是根据删除顺序的倒叙来建树，最后dfs序即可，然后用线段树维护答案
代码：
#include<bits/stdc++.h> #define xx first #define yy second #define mp make_pair #define pb push_back using namespace std; typedef long long ll; typedef pair<int,int> pii; const int MAXN=5e5+5; const int MAXM=3e5+5; const int MAXQ=5e5+5; vector<int> E[MAXN]; int n,m,q; pii e[MAXM],mdf[MAXQ]; int p[MAXN],in[MAXN],out[MAXN]; bool vis[MAXM]; int tim=0; struct DSU { int fa[MAXN]; void init(int n) { for(int i=1;i<=n;i++) fa[i]=i; } int find(int x) { if(x^fa[x]) return fa[x]=find(fa[x]); return x; } void merge(int x,int y) { x=find(x); y=find(y); if(x==y) return ; ++n; fa[n]=n;fa[x]=n;fa[y]=n; E[n].pb(x);E[n].pb(y); } }dsu; struct seg { #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 pii mx[MAXN<<2]; inline void push_up(int rt) { mx[rt]=max(mx[rt<<1],mx[rt<<1|1]); } void update(int pos,pii val,int l,int r,int rt) { if(l==r) { mx[rt]=val; return ; } int mid=(l+r)>>1; if(pos<=mid) update(pos,val,lson); if(mid<pos) update(pos,val,rson); push_up(rt); } pii query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) return mx[rt]; int mid=(l+r)>>1; pii ret(0,0); if(L<=mid) ret=max(ret,query(L,R,lson)); if(mid<R) ret=max(ret,query(L,R,rson)); return ret; } }se; void dfs(int now,int fa) { in[now]=++tim; for(auto v:E[now]) { if(v==fa) continue; dfs(v,now); } out[now]=tim; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;i++) scanf("%d",&p[i]); for(int i=1;i<=m;i++) scanf("%d%d",&e[i].xx,&e[i].yy); for(int i=1;i<=q;i++) { scanf("%d%d",&mdf[i].xx,&mdf[i].yy); if(mdf[i].xx==2) vis[mdf[i].yy]=1; } dsu.init(n); for(int i=1;i<=m;i++) if(!vis[i]) dsu.merge(e[i].xx,e[i].yy); for(int i=q;i>=1;i--) { if(mdf[i].xx==1) { mdf[i].yy=dsu.find(mdf[i].yy); } else { int id=mdf[i].yy; dsu.merge(e[id].xx,e[id].yy); } } for(int i=1;i<=n;i++) if(dsu.find(i)==i) dfs(i,0); for(int i=1;i<=n;i++) se.update(in[i],{p[i],in[i]},1,n,1); for(int i=1;i<=q;i++) { if(mdf[i].xx==1) { int id=mdf[i].yy; pii res=se.query(in[id],out[id],1,n,1); printf("%d\n",res.xx); if(res.yy) se.update(res.yy,{0,0},1,n,1); } } return 0; }
