BZOJ-3123: [Sdoi2013]森林

Description

一个森林，有n个带有点权的点，m次操作：
1.Q x y k，询问x到y的所有权值中第k小的是多少
2.L x y，将x,y连接一条边，保证连接之后仍然是森林。
强制在线，n,m<=8*10^4

启发式合并+主席树+倍增求lca+并查集
对每个点主席树维护其到根路径上所有点权的权值线段树。每次连边的时候，将小的树接到大的树上，重新建树以及求倍增数组，这样的话，每个点至多被插入logn次，倍增数组至多修改logn次，总复杂度

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 80100 

int n,m,q,a[N],b[N],f[N],siz[N];
int head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
    to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt;
}
int find(int x){return x==f[x] ? x:f[x]=find(f[x]);}

struct seg
{
    int ls,rs,s;
}t[N*400];
int se,rt[N];
void insert(int &r1,int r2,int l,int r,int x)
{
    r1=++se; t[r1].s=t[r2].s+1;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(x<=mid) t[r1].rs=t[r2].rs,insert(t[r1].ls,t[r2].ls,l,mid,x);
    else t[r1].ls=t[r2].ls,insert(t[r1].rs,t[r2].rs,mid+1,r,x);
}
int query(int r1,int r2,int r3,int r4,int l,int r,int x)
{
    if(l==r) return b[l];
    int s=t[t[r1].ls].s+t[t[r2].ls].s-t[t[r3].ls].s-t[t[r4].ls].s;
    int mid=(l+r)>>1;
    if(x<=s) return query(t[r1].ls,t[r2].ls,t[r3].ls,t[r4].ls,l,mid,x);
    x-=s; return query(t[r1].rs,t[r2].rs,t[r3].rs,t[r4].rs,mid+1,r,x);
}

int Log[N],dep[N],fa[N][20];
void dfs(int x,int pre)
{
    dep[x]=dep[pre]+1; fa[x][0]=pre;
    for(int i=1;i<=19;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
    insert(rt[x],rt[pre],1,n,a[x]);
    for(int i=head[x];i;i=nxt[i])
        if(to[i]!=pre)
            dfs(to[i],x);
}
int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=Log[dep[x]];~i;--i)
        if(dep[fa[x][i]]>=dep[y])
            x=fa[x][i];
    if(x==y) return x;
    for(int i=Log[dep[x]];~i;--i)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

int main()
{
    scanf("%*d%d%d%d",&n,&m,&q);
    int i;
    for(i=1;i<=n;++i) scanf("%d",a+i),b[i]=a[i];
    sort(b+1,b+n+1);
    for(i=1;i<=n;++i) a[i]=lower_bound(b+1,b+n+1,a[i])-b,f[i]=i,siz[i]=1;
    int x,y;
    while(m--)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        f[find(x)]=find(y);
        siz[find(y)]+=siz[find(x)];
    }
    for(i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
    for(i=1;i<=n;++i) if(find(i)==i) dfs(i,0);
    char sw[10]; int k,ans=0,anc;
    while(q--)
    {
        scanf("%s%d%d",sw,&x,&y); x^=ans; y^=ans;
        if(sw[0]=='Q')
        {
            scanf("%d",&k); k^=ans; anc=lca(x,y);
            printf("%d\n",ans=query(rt[x],rt[y],rt[anc],rt[fa[anc][0]],1,n,k));
        }
        else
        {
            add(x,y);
            if(siz[find(x)]>siz[find(y)]) swap(x,y);
            dfs(x,y); f[find(x)]=find(y); siz[find(y)]+=siz[find(x)];
        }
    }
    return 0;
}