题目
蜘蛛精大爷是世界上最爷的爷，ta的图论专著《蜘蛛精大爷教你学做人OI之图论》正在热卖，只要233美元一本，每人限购一本。。。。。。在某弱的不懈要求下，ta给某弱出了一道题，然而某弱太弱了，只好向你求助。
给你一张n个结点，m条边的无向图，每个结点都有一个整数权值。你需要执行一系列操作。操作分为三种，如下表所示。
操作
D x (1<=x<=m)
删除编号为x的边。输入保证每条边至多被删除一次。
Q x k (1<=x<=n)
计算出结点x所在的联通块中，第k大的权值。如果不存在，输出0。
C x v (1<=x<=n)
把结点x的权值改为v。
操作序列的结束标志为单个字母E。结点编号为1到n，边的编号为1到m。
分析
考虑到，求第k大，我们可以用权值线段树，
线段树分裂很麻烦，
所以，倒过来做。
首先先将没有被删除的边加入，用并查集维护，
对于每一个联通块开一棵线段树，
在将经过多次修改后的权值扔进这个节点所在的联通块的线段树。
这就是初始化了。
每当有D操作，如果这条边两边的点不在同一个联通块，用并查集并在一起，并将两个联通块的线段树合并。
Q操作就直接查询，记录在一个数组，最后倒着输出。
C操作，就在线段树中删除该值，加入修改前的值。
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const long long maxlongint=2147483647ll;
const long long mo=1000000007;
const long long N=2000005;
const long long M=60010;
using namespace std;
long long tr[N][2],root[N],fa[N],b[N][2],size[N],n,m,re[N][3],tot,num,sum,d[N+10],t,v[N];
long long ans[N];
bool bz[N]={0};
long long read(long long &n)
{
char ch=' ';int q=0,w=1;
for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
if(ch=='-')w=-1,ch=getchar();
for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
void put(long long v,long long l,long long r,long long x,long long y)
{
if(l==r)
{
size[v]+=y;
return;
}
long long mid=(l+r)/2;
if(x<=mid)
{
if(!tr[v][0]) tr[v][0]=++tot;
put(tr[v][0],l,mid,x,y);
}
else
{
if(!tr[v][1]) tr[v][1]=++tot;
put(tr[v][1],mid+1,r,x,y);
}
size[v]+=y;
}
long long get(long long x)
{
if(fa[x]==x) return x;
return (fa[x]=get(fa[x]));
}
long long mesh(long long x,long long y)
{
if (!x) return y;
if (!y) return x;
size[x]+=size[y];
tr[x][0]=mesh(tr[x][0],tr[y][0]);
tr[x][1]=mesh(tr[x][1],tr[y][1]);
return x;
}
bool qq=true;
long long find(long long v,long long l,long long r,long long y)
{if(l==r) return l;
long long mid=(l+r)/2;
if(y<=size[tr[v][1]]) return find(tr[v][1],mid+1,r,y);
else
return find(tr[v][0],l,mid,y-size[tr[v][1]]);
}
int main()
{
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++)
read(v[i]),fa[i]=i,root[i]=++tot;
for(long long i=1;i<=m;i++)
for(long long j=0;j<=1;j++) read(b[i][j]);
while(1)
{
char c=getchar();
while(c!='E' && c!='D' && c!='Q' && c!='C') c=getchar();
if(c=='E') break;
read(re[++num][1]);
if(c=='D') bz[re[num][1]]=true;
else
if(c=='Q') re[num][0]=1,read(re[num][2]);
else
{
re[num][0]=2,read(re[num][2]);
long long x=re[num][2];
re[num][2]=v[re[num][1]];
v[re[num][1]]=x;
}
}
long long ff=maxlongint*2;
for(long long i=1;i<=n;i++) v[i]+=maxlongint;
for(int i=1;i<=num;i++)
if(re[i][0]==2) re[i][2]+=maxlongint;
for(int i=1;i<=m;i++)
if(!bz[i]) fa[get(b[i][1])]=get(b[i][0]);
for(int i=1;i<=n;i++) put(root[get(i)],0,ff,v[i],1);
for(int i=num;i>=1;i--)
{
if(!re[i][0])
{
int z=re[i][1],xx=get(b[z][0]),yy=get(b[z][1]);
if(xx==yy) continue;
mesh(root[xx],root[yy]);
fa[yy]=xx;
}
else
if(re[i][0]==1)
{
if(re[i][2]>size[root[get(re[i][1])]]) ans[++sum]=maxlongint;
else ans[++sum]=find(root[get(re[i][1])],0,maxlongint*2,re[i][2]);
qq=false;
}
else
{
put(root[get(re[i][1])],0,ff,v[re[i][1]],-1);
v[re[i][1]]=re[i][2];
put(root[get(re[i][1])],0,ff,v[re[i][1]],1);
}}
for(int i=sum;i>=1;i--) printf("%lld\n",ans[i]-maxlongint);
}
