启发式合并主席树

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define N 80001int n,testcase,m,T;int val[N];int front[N],to[N<<1],nxt[N<<1],tot;int has[N],all;int fa[N][17],dep[N],lim;int F[N],siz[N];int id,root[N];    struct node{    int lc,rc,cnt;}tr[N*200];void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}void add(int u,int v){    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;}int find(int i) { return F[i]==i ? i : F[i]=find(F[i]); }void unionn(int u,int v){    u=find(u); v=find(v);    siz[u]+=siz[v];    F[v]=u;}void init(){    read(testcase);    read(n); read(m); read(T);    lim=log(n)/log(2);    for(int i=1;i<=n;++i)     {        read(val[i]);        F[i]=i;        siz[i]=1;    }    int u,v;    for(int i=1;i<=m;++i)    {        read(u); read(v);        add(u,v);        unionn(u,v);    }}    void insert(int &x,int y,int l,int r,int pos){    if(!x) x=++id;    tr[x].cnt=tr[y].cnt+1;    if(l==r) return;    int mid=l+r>>1;    if(pos<=mid)     {        tr[x].rc=tr[y].rc;        insert(tr[x].lc,tr[y].lc,l,mid,pos);    }    else    {        tr[x].lc=tr[y].lc;        insert(tr[x].rc,tr[y].rc,mid+1,r,pos);    }}int query(int u,int v,int lca,int flca,int l,int r,int k){    if(l==r) return l;    int mid=l+r>>1,tmp=tr[tr[u].lc].cnt+tr[tr[v].lc].cnt-tr[tr[lca].lc].cnt-tr[tr[flca].lc].cnt;    if(k<=tmp) return query(tr[u].lc,tr[v].lc,tr[lca].lc,tr[flca].lc,l,mid,k);               return query(tr[u].rc,tr[v].rc,tr[lca].rc,tr[flca].rc,mid+1,r,k-tmp);}    void discrete(){    for(int i=1;i<=n;++i) has[i]=val[i];    sort(has+1,has+n+1);    all=unique(has+1,has+n+1)-has-1;    for(int i=1;i<=n;++i) val[i]=lower_bound(has+1,has+all+1,val[i])-has;}    void dfs(int x){    dep[x]=dep[fa[x][0]]+1;    insert(root[x],root[fa[x][0]],1,all,val[x]);    for(int i=1;i<=lim;++i) fa[x][i]=fa[fa[x][i-1]][i-1];    for(int i=front[x];i;i=nxt[i])        if(to[i]!=fa[x][0])        {            fa[to[i]][0]=x;            dfs(to[i]);        }}int get_lca(int u,int v){    if(dep[u]
          
           =0;--i) if(x&(1<
           
            =0;--i) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0];}void solve(){ for(int i=1;i<=n;++i) if(!fa[i][0]) dfs(i); char ch[3]; int u,v,k,last=0; int lca,fu,fv; while(T--) { scanf("%s",ch); if(ch[0]=='Q') { read(u); read(v); read(k); u^=last; v^=last; k^=last; lca=get_lca(u,v); last=has[query(root[u],root[v],root[lca],root[fa[lca][0]],1,all,k)]; printf("%d\n",last); } else { read(u); read(v); u^=last; v^=last; fu=find(u); fv=find(v); if(siz[fu]