Description
.jpg)
Input
第一行包含一个正整数testcase，表示当前测试数据的测试点编号。保证1≤testcase≤20。
第二行包含三个整数N，M，T，分别表示节点数、初始边数、操作数。第三行包含N个非负整数表示 N个节点上的权值。
接下来 M行，每行包含两个整数x和 y，表示初始的时候，点x和点y 之间有一条无向边, 接下来 T行，每行描述一个操作，格式为“Q x y k”或者“L x y ”，其含义见题目描述部分。
Output
对于每一个第一类操作，输出一个非负整数表示答案。
对每个联通块用倍增维护树的结构，可持久化线段树支持查询树链上第k小，修改时可以启发式合并
#include<cstdio> #include<algorithm> const int N=80007; char buf[20000007],*ptr=buf-1; #define G *++ptr int _(){ int x=0,c=G; while(c<48)c=G; while(c>47)x=x*10+c-48,c=G; return x; } int _c(){ int c=G; while(c<33)c=G; return c; } int n,m,q,la=0,v[N],vs[N],f[N],siz[N],rt[N]; int es[N*2],enx[N*2],e0[N],ep=2; int fa[N][20],dep[N]; int ch[N*400][2],sz[N*400],mp=0; int gf(int x){ while(x!=f[x])x=f[x]=f[f[x]]; return x; } int ins(int w,int x){ int u=++mp,u0=u; for(int i=16,d;~i;--i){ d=x>>i&1; ch[u][d^1]=ch[w][d^1]; sz[u=ch[u][d]=++mp]=sz[w=ch[w][d]]+1; } return u0; } void f1(int w,int pa=0){ dep[w]=dep[fa[w][0]=pa]+1; rt[w]=ins(rt[pa],v[w]); for(int i=1;i<17;++i)fa[w][i]=fa[fa[w][i-1]][i-1]; for(int i=e0[w];i;i=enx[i]){ int u=es[i]; if(u!=pa)f1(u,w); } } void mg(int a,int b,bool d){ int x=gf(a),y=gf(b); if(siz[x]>siz[y])std::swap(x,y),std::swap(a,b); siz[f[x]=y]+=siz[x]; if(d)f1(a,b); es[ep]=a;enx[ep]=e0[b];e0[b]=ep++; es[ep]=b;enx[ep]=e0[a];e0[a]=ep++; } int up(int x,int d){ for(int t=0;d;d>>=1,++t)if(d&1)x=fa[x][t]; return x; } int lca(int a,int b){ if(dep[a]<dep[b])std::swap(a,b); a=up(a,dep[a]-dep[b]); if(a!=b){ for(int i=16;~i;--i)if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i]; return fa[a][0]; } return a; } void query(int w1,int w2,int w3,int w4,int k){ int x=0; for(int i=16;~i;--i){ int s=sz[ch[w1][0]]+sz[ch[w2][0]]-sz[ch[w3][0]]-sz[ch[w4][0]]; if(s>=k){ w1=ch[w1][0]; w2=ch[w2][0]; w3=ch[w3][0]; w4=ch[w4][0]; }else{ x|=1<<i; k-=s; w1=ch[w1][1]; w2=ch[w2][1]; w3=ch[w3][1]; w4=ch[w4][1]; } } printf("%d ",la=vs[x]); } int main(){ buf[fread(buf,1,sizeof(buf),stdin)]=0; _(); n=_();m=_();q=_(); for(int i=1;i<=n;++i)vs[i]=v[i]=_(),siz[i]=dep[i]=1,f[i]=i; std::sort(vs+1,vs+n+1); for(int i=1;i<=n;++i)v[i]=std::lower_bound(vs+1,vs+n+1,v[i])-vs; while(m--)mg(_(),_(),0); for(int i=1;i<=n;++i)if(i==f[i])f1(i,0); while(q--){ if(_c()=='Q'){ int x=_()^la,y=_()^la,k=_()^la,z=lca(x,y); query(rt[x],rt[y],rt[z],rt[fa[z][0]],k); }else{ int x=_()^la,y=_()^la; mg(x,y,1); } } return 0; }