题面

洛谷P3302

Solution

拿到这道题，我们不妨先想一下静态的树上K大怎么搞。
静态树上K大有两种办法，一是树链剖分+平衡树，二是主席树做链前缀和。前者的复杂度是$O(log^2n)$的，而后者只有$O(logn)$。

我们考虑把数字全部离散化，然后开权值主席树，每颗主席树记录从它出发到根的路上每个数字出现了多少个。接下来，我们只需要找到LCA。因为数字出现个数满足可减性，因此，我们是可以“扣”出从这个点到LCA的路径的，我们把两条路径合并到一颗主席树上，做树上二分即可。

接下来考虑如何处理边合并的问题。考虑启发式暴力合并。我们把小的那棵树合并到大的那棵树上，暴力重构小的那棵树的每个点的主席树，也暴力重构每个点的depth，fa来计算LCA即可。

启发式合并中，每个点的重构次数期望为$logn$次，因此，我们的总复杂度为$O(nlog^2n)$

就酱，这题我们就切掉啦(～￣▽￣)～

Code

细节繁多，请各位dalao小心

//Luogu P3302 [SDOI2013]森林
//Mar,6th,2019
//主席树启发式合并维护动态树树链K大
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
long long read()
{
    long long x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N=80000+2000;
struct SegmentTree
{
    #define mid ((now_l+now_r)>>1)
    static const int M=400*N;
    int son[M][2],size[M],to;
    inline void update(int now)
    {
        size[now]+=size[son[now][0]]+size[son[now][1]];
    }
    inline void Add(int now,int pre,int x,int now_l,int now_r)
    {
        if(now_l==now_r)
        {
            size[now]=size[pre]+1;
            return;
        }
        if(x<=mid) 
        {
            Add(son[now][0]=++to,son[pre][0],x,now_l,mid);
            son[now][1]=son[pre][1];
        }
        else
        {
            Add(son[now][1]=++to,son[pre][1],x,mid+1,now_r);
            son[now][0]=son[pre][0];
        }
        update(now);
    }
    int Query(int now1,int now2,int pre1,int pre2,int x,int now_l,int now_r)
    {
        if(now_l==now_r) return now_l;
        if(x<=size[son[now1][0]]-size[son[pre1][0]]+size[son[now2][0]]-size[son[pre2][0]])
            return Query(son[now1][0],son[now2][0],son[pre1][0],son[pre2][0],x,now_l,mid);
        else
            return Query(son[now1][1],son[now2][1],son[pre1][1],son[pre2][1],x-(size[son[now1][0]]-size[son[pre1][0]]+size[son[now2][0]]-size[son[pre2][0]]),mid+1,now_r);
    }
    void Print(int now,int now_l,int now_r)
    {
        cerr<<"no."<<now<<" l&r:"<<now_l<<" "<<now_r<<" sonl&r:"<<son[now][0]<<" "<<son[now][1]<<" size:"<<size[now]<<endl;
        if(now_l!=now_r)
            Print(son[now][0],now_l,mid),
            Print(son[now][1],mid+1,now_r);
    }
    #undef mid
}sgt;
vector <int> e[N];
int n,m,q,w[N],mmap[N];//mmap:离散值->真实值
int fa[N][21],size[N],depth[N],root[N];
bool vis[N];
void dfs(int now)
{
    for(int i=1;i<=20;i++)
        fa[now][i]=fa[fa[now][i-1]][i-1];
    vis[now]=true;
    for(int i=0;i<int(e[now].size());i++)
        if(vis[e[now][i]]==false)
        {
            depth[e[now][i]]=depth[now]+1;
            fa[e[now][i]][0]=now;
            root[e[now][i]]=++sgt.to;
            sgt.Add(root[e[now][i]],root[now],w[e[now][i]],1,m);
            //sgt.Print(root[e[now][i]],1,m);
            //cerr<<endl;
            dfs(e[now][i]);
        }
    vis[now]=false;
}
void Merge(int x,int y)
{
    if(size[fa[x][20]]>size[fa[y][20]]) swap(x,y);
    size[fa[y][20]]+=size[fa[x][20]];
    depth[x]=depth[y]+1;
    fa[x][0]=y;
    root[x]=++sgt.to;
    sgt.Add(root[x],root[y],w[x],1,m);
    //sgt.Print(root[x],1,m);
    //cerr<<endl;
    dfs(x);
    e[x].push_back(y);
    e[y].push_back(x);
}
int LCA(int x,int y)
{
    if(depth[x]<depth[y]) swap(x,y);
    for(int i=20;i>=0;i--)
        if(depth[fa[x][i]]>=depth[y])
            x=fa[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int Query(int x,int y,int K)
{
    if(depth[x]<depth[y]) swap(x,y);
    int lca=LCA(x,y);
    if(lca==y)
        return mmap[sgt.Query(root[x],0,(fa[lca][0]==lca?0:root[fa[lca][0]]),0,K,1,m)];
    else
        return mmap[sgt.Query(root[x],root[y],root[lca],(fa[lca][0]==lca?0:root[fa[lca][0]]),K,1,m)];
}
void Init()
{
    for(int i=0;i<=n;i++)
        e[i].reserve(4);
    for(int i=1;i<=n;i++)
    {
        root[i]=++sgt.to;
        sgt.Add(root[i],0,w[i],1,m);
    }
    for(int i=1;i<=n;i++)
        size[i]=1,depth[i]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=21;j++)
            fa[i][j]=i;
}
int m2;
int main()
{
    static int tmp[N];
    n=read(),n=read(),m2=read(),q=read();
    for(int i=1;i<=n;i++)
        tmp[i]=w[i]=read();

    sort(tmp+1,tmp+1+n);
    m=unique(tmp+1,tmp+1+n)-tmp-1;
    for(int i=1;i<=n;i++)
    {
        int temp=lower_bound(tmp+1,tmp+1+m,w[i])-tmp;
        mmap[temp]=w[i];
        w[i]=temp;
    }
    Init();

    for(int i=1;i<=m2;i++)
    {
        int x=read(),y=read();
        Merge(x,y);
    }

    int ans=0;
    char OP[5];
    for(int i=1;i<=q;i++)
    {
        scanf("%s",OP+1);
        if(OP[1]=='Q')
        {
            int x=read()^ans,y=read()^ans,K=read()^ans;
            printf("%d\n",ans=Query(x,y,K));
        }
        else
        {
            int x=read()^ans,y=read()^ans;
            Merge(x,y);
        }
        //ans=0;
    }
    return 0;
}