思路

恶心人的题目

还是类似永无乡一题的Treap启发式合并思路

但是由于加边变成了删边

所以应该离线后倒序处理

数组要开够

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;int Nodecnt=0,root[250000*2],fa[250000*2],w_p[250000*2],cnt,n,m;struct Edge{ int u,v;}E[250000*2];struct oper{ int opt,x,k,v;}Ask[250000*2];struct Node{ int lson,rson,sz,val,ran;}Treap[250000*2];set
          
            use;stack
           
             ans;int find(int x){ if(fa[x]==x) return x; else return fa[x]=find(fa[x]);}queue
            
              q;void throwin(int x){ q.push(x);}int getnew(int val){ int o; if(q.size()) o=q.front(),q.pop(); else o=++Nodecnt; Treap[o].lson=Treap[o].rson=0; Treap[o].sz=1; Treap[o].ran=rand(); Treap[o].val=val; return o;}void pushup(int o){ Treap[o].sz=Treap[Treap[o].lson].sz+Treap[Treap[o].rson].sz+1;}void rorateL(int &o){ int x=Treap[o].rson; Treap[o].rson=Treap[x].lson; Treap[x].lson=o; pushup(o); pushup(x); o=x;}void rorateR(int &o){ int x=Treap[o].lson; Treap[o].lson=Treap[x].rson; Treap[x].rson=o; pushup(o); pushup(x); o=x;}void insert(int val,int &o){ if(!o){ o=getnew(val); return; } Treap[o].sz++; if(val<=Treap[o].val){ insert(val,Treap[o].lson); if(Treap[Treap[o].lson].ran
             
              Treap[Treap[o].rson].sz+1) return query(val-Treap[Treap[o].rson].sz-1,Treap[o].lson); else return query(val,Treap[o].rson);}void dfs(int &o,int to){ if(!o) return; insert(Treap[o].val,root[to]); dfs(Treap[o].lson,to); dfs(Treap[o].rson,to); throwin(o); o=0;}void init(void){ Nodecnt=0; cnt=0; memset(Treap,0,sizeof(Treap)); memset(root,0,sizeof(root)); memset(fa,0,sizeof(fa)); memset(w_p,0,sizeof(w_p)); memset(E,0,sizeof(E)); memset(Ask,0,sizeof(Ask)); while(!q.empty()) q.pop(); use.clear();}int main(){ freopen("test.in","r",stdin); freopen("test.out","w",stdout); int inq=0; while(scanf("%d %d",&n,&m)==2){ inq++; if(n==0&&m==0) break; init(); for(int i=1;i<=n;i++){ scanf("%d",&w_p[i]); fa[i]=i; } for(int i=1;i<=m;i++) scanf("%d %d",&E[i].u,&E[i].v),use.insert(i); char opt=getchar(); while(opt!='E'&&opt!='Q'&&opt!='C'&&opt!='D') opt=getchar(); while(opt!='E'){ ++cnt; if(opt=='D'){ Ask[cnt].opt=1; scanf("%d",&Ask[cnt].x); use.erase(Ask[cnt].x); } else if(opt=='Q'){ Ask[cnt].opt=2; scanf("%d %d",&Ask[cnt].x,&Ask[cnt].k); } else if(opt=='C'){ Ask[cnt].opt=3; scanf("%d %d",&Ask[cnt].x,&Ask[cnt].v); int t=w_p[Ask[cnt].x]; w_p[Ask[cnt].x]=Ask[cnt].v; Ask[cnt].v=t; } opt=getchar(); while(opt!='E'&&opt!='Q'&&opt!='C'&&opt!='D') opt=getchar(); } for(int i=1;i<=n;i++) insert(w_p[i],root[i]); for(auto it = use.begin();it!=use.end();it++){ int a=E[(*it)].u,b=E[(*it)].v; if(find(a)!=find(b)){ if(Treap[root[find(a)]].sz
              
               =1;i--){ if(Ask[i].opt==1){ int a=E[Ask[i].x].u,b=E[Ask[i].x].v; if(find(a)!=find(b)){ if(Treap[root[find(a)]].sz