codevs 951 森林

http://codevs.cn/problem/1951/

2013年省队选拔赛

#include<cstdio>#include<algorithm>#define N 160001using namespace std;int t,n,m,q,tot,edge_tot,tree_tot,cnt;int key[N],hashh[N],deep[N],F[N],siz[N*75],siz_b[N],lc[N*75],rc[N*75],ancestor[N][26],root[N];int front[N],nextt[N*2],to[N*2];int read(){    int x=0;char c=getchar();    while(c<‘0‘||c>‘9‘) c=getchar();    while(c>=‘0‘&&c<=‘9‘) {x=x*10+c-‘0‘;c=getchar();}    return x;}int find(int x) {return x==F[x] ? x:F[x]=find(F[x]);}void discrete(){    sort(key+1,key+n+1);    tot=unique(key+1,key+n+1)-(key+1);}void add(int u,int v){    to[++edge_tot]=v;nextt[edge_tot]=front[u];front[u]=edge_tot;}void insert(int pre,int &x,int l,int r,int w){    siz[x=++tree_tot]=siz[pre]+1;    if(l==r) return;    int mid=l+r>>1;    if(w<=mid)    {        rc[x]=rc[pre];        insert(lc[pre],lc[x],l,mid,w);    }    else    {        lc[x]=lc[pre];        insert(rc[pre],rc[x],mid+1,r,w);    }}void dfs(int now,int f){    ancestor[now][0]=f;siz_b[now]=1;    int p=lower_bound(key+1,key+tot+1,hashh[now])-key;    insert(root[f],root[now],1,tot,p);    for(int i=front[now];i;i=nextt[i])    {        if(to[i]==f) continue;        deep[to[i]]=deep[now]+1;        dfs(to[i],now);        siz_b[now]+=siz_b[to[i]];    }}int get_same(int x,int y){    for(int i=0;i<=20;i++)     if(y&(1<<i)) x=ancestor[x][i];    return x;  }int get_lca(int x,int y){    if(deep[x]<deep[y]) swap(x,y);    x=get_same(x,deep[x]-deep[y]);    if(x==y) return x;    for(int i=20;i>=0;i--)     if(ancestor[x][i]!=ancestor[y][i])       {           x=ancestor[x][i];y=ancestor[y][i];      }    return ancestor[x][0];}int query(int x,int y,int lca,int flca,int l,int r,int k){    if(l==r) return l;    int mid=l+r>>1,tmp=siz[lc[x]]+siz[lc[y]]-siz[lc[lca]]-siz[lc[flca]];    if(k<=tmp) return query(lc[x],lc[y],lc[lca],lc[flca],l,mid,k);    else return query(rc[x],rc[y],rc[lca],rc[flca],mid+1,r,k-tmp);}void unionn(int x,int y){    ancestor[y][0]=x;deep[y]=deep[x]+1;    int p=lower_bound(key+1,key+tot+1,hashh[y])-key;    insert(root[x],root[y],1,tot,p);    for(int i=1;i<=20;i++) ancestor[y][i]=ancestor[ancestor[y][i-1]][i-1];    for(int i=front[y];i;i=nextt[i])    {        if(to[i]==x) continue;        unionn(y,to[i]);     }}void get_ancestor(){    for(int i=1;i<=20;i++)     for(int j=1;j<=n;j++)      ancestor[j][i]=ancestor[ancestor[j][i-1]][i-1];}int main(){    //scanf("%d%d%d%d",&t,&n,&m,&q);    t=read();n=read();m=read();q=read();        for(int i=1;i<=n;i++)    {        //scanf("%d",&key[i]);        key[i]=read();        F[i]=i;hashh[i]=key[i];    }    int x,y,z,last=0;    char c[2];    for(int i=1;i<=m;i++)    {        //scanf("%d%d",&x,&y);        x=read();y=read();        int r1=find(x),r2=find(y);        F[r1]=r2;        add(y,x);add(x,y);    }    discrete();    for(int i=1;i<=n;i++) if(!ancestor[i][0]) dfs(i,0);    get_ancestor();    for(int i=1;i<=q;i++)    {        scanf("%s",c);        if(c[0]==‘Q‘)        {            //scanf("%d%d%d",&x,&y,&z);            x=read();y=read();z=read();            x^=last;y^=last;z^=last;            int lca=get_lca(x,y);            last=query(root[x],root[y],root[lca],root[ancestor[lca][0]],1,tot,z);            last=key[last];            printf("%d\n",last);        }        else        {            //scanf("%d%d",&x,&y);            x=read();y=read();            x^=last;y^=last;            int r1=find(x),r2=find(y);            if(siz_b[r1]<siz_b[r2]) swap(r1,r2),swap(x,y);            F[r2]=r1;siz_b[r1]+=siz_b[r2];            add(x,y);add(y,x);            unionn(x,y);        }    }}