给定n个点，每个点有权值，操作会联通某两个点的联通块，或询问某联通块中的第k大的点。
对每个点维护一个平衡树，对于联通的操作启发式合并，把size小的树每个点暴力拆开，插入到size大的树中。
#include <cstdio>#include <iostream>#include <cstdlib>#include <algorithm>#define N 200010using namespace std;int n,m,x,y,q;char op;struct lef{ lef *fa,*ch[2]; int sz,r,w,g;}p[N],*rt,*u,*v,*city[N];inline void updat(lef *x){ if(!x) return; x->sz=1; if(x->ch[0]) x->sz+=x->ch[0]->sz; if(x->ch[1]) x->sz+=x->ch[1]->sz;}inline void *reborn(lef *x){ x->fa=x->ch[0]=x->ch[1]=NULL; x->sz=1;}inline void rot(lef *x){ lef *y=x->fa,*z=y->fa; int lor=x==y->ch[1]; if(z) z->ch[z->ch[1]==y]=x; x->fa=z; if(y->ch[lor]=x->ch[lor^1]) y->ch[lor]->fa=y; (x->ch[lor^1]=y)->fa=x; updat(y); updat(x);}inline void InserT(lef *&x,lef *y){ if(!x){x=y;return ;} x->sz++; if(x->w>y->w){ InserT(x->ch[0],y); x->ch[0]->fa=x; if(x->r>x->ch[0]->r) rot(x->ch[0]); } else{ InserT(x->ch[1],y); x->ch[1]->fa=x; if(x->r>x->ch[1]->r) rot(x->ch[1]); }}inline char C(){ static char buf[100000],*p1=buf,*p2=buf; if(p1==p2){ p2=(p1=buf)+fread(buf,1,100000,stdin); if(p1==p2) return EOF; } return *p1++;}inline void reaD(int &x){ char Ch=C();x=0; for(;Ch>'9'||Ch<'0';Ch=C()); for(;Ch>='0'&&Ch<='9';x=x*10+Ch-'0',Ch=C());}inline lef *Getrt(lef *x){ if(!x) return NULL; while(x->fa) x=x->fa; return x;}void merge(lef *x,lef *y){ if(x->ch[0]) merge(x->ch[0],y); if(x->ch[1]) merge(x->ch[1],y); reborn(x); InserT(y,x);}int check(lef *x,int y){ int k=1; if(x->ch[0]) k+=x->ch[0]->sz; if(k==y) return x->g; if(k<y) return check(x->ch[1],y-k); else check(x->ch[0],y);}int main(){ freopen("2733.in","r",stdin); freopen("2733.out","w",stdout); reaD(n);reaD(m); for(int i=1;i<=n;i++){ city[i]=&p[i]; reaD(city[i]->w); city[i]->r=rand(); city[i]->g=i; city[i]->sz=1; } for(int i=1;i<=m;i++){ reaD(x); reaD(y); u=Getrt(city[x]); v=Getrt(city[y]); if(u==v) continue; if(u->sz>v->sz) swap(u,v); merge(u,v); } reaD(q); for(int i=1;i<=q;i++){ while((op=C())!='Q'&&op!='B'); if(op=='B'){ reaD(x);reaD(y); u=Getrt(city[x]); v=Getrt(city[y]); if(u==v) continue; if(u->sz>v->sz) swap(u,v); merge(u,v); } else{ reaD(x);reaD(y); u=Getrt(city[x]); if(!u||y>u->sz) puts("-1"); else PRintf("%d/n",check(u,y)); } }}新闻热点
疑难解答
