树上主席树（在线）洛谷3302

水深无声 2023-06-04 06:59 12阅读 0赞

小Z有一片森林，含有N个节点，每个节点上都有一个非负整数作为权值。初始的时候，森林中有M条边。

小Z希望执行T个操作，操作有两类：

1.  `Q x y k`查询点x到点y路径上所有的权值中，第k小的权值是多少。此操作保证点x和点y连通，同时这两个节点的路径上至少有k个点。
2.  `L x y`在点x和点y之间连接一条边。保证完成此操作后，仍然是一片森林。

为了体现程序的在线性，我们把输入数据进行了加密。设lastans为程序上一次输出的结果，初始的时候lastans为0。

*  对于一个输入的操作`Q x y k`,其真实操作为`Q x^lastans y^lastans k^lastans`。
 *  对于一个输入的操作`L x y`，其真实操作为`L x^lastans y^lastans`。其中^运算符表示异或，等价于pascal中的xor运算符。

请写一个程序來帮助小Z完成这些操作。

对于所有的数据，n,m,T<=8\*10^48∗104.

思路：离散化，小树建立到大树上，暴力修改小树主席树，每个点都是一个主席树，树套树

#include <bits/stdc++.h>
    using namespace std;
    const int N=8e4+5;
    int T,n,m,TT,last;
    int tot,row[N],s[N],size[N];
    int cnt,to[4*N],nxt[4*N],head[4*N];
    int from[N],lg[N],ans[N][35],deep[N];
    struct Tree{
        int ls,rs,si;
    }t[105*N];
    int root[N],top;
    
    int in(){
        int x=0,f=1;char ch=getchar();
        while(ch>'9'||ch<'0'){ if(ch=='-') f=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
        return x*f; 
    }
    
    void adds(int x,int y){
        to[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;
        return;
    }
    
    void pre_work(){
        int a,b;lg[0]=-1;
        T=in();n=in();m=in();TT=in();
        for(int i=1;i<=n;i++)
            row[i]=s[i]=in(),lg[i]=lg[i>>1]+1,from[i]=i;    
        sort(row+1,row+1+n);
        tot=unique(row+1,row+1+n)-(row+1);
        for(int i=1;i<=n;i++)
            s[i]=lower_bound(row+1,row+1+tot,s[i])-row; 
        for(int i=1;i<=m;i++)
            a=in(),b=in(),adds(a,b),adds(b,a);
        return;
    }
    
    void built(int &pos,int pre,int l,int r,int wi){
        t[pos=++top]=t[pre];
        t[pos].si++;
        if(l==r) return;
        int mid=(l+r)>>1;
        if(wi<=mid) built(t[pos].ls,t[pre].ls,l,mid,wi);
        else built(t[pos].rs,t[pre].rs,mid+1,r,wi);
        return;
    }
    
    void dfs(int u,int fa,int rt){
        built(root[u],root[fa],1,tot,s[u]);
        deep[u]=deep[fa]+1;ans[u][0]=fa;
        size[rt]++;from[u]=rt;
        for(int i=1;i<=18;i++)
            ans[u][i]=ans[ans[u][i-1]][i-1];
        for(int i=head[u];i;i=nxt[i])
            if(to[i]!=fa) dfs(to[i],u,rt);
        return;
    }
    
    int get_LCA(int u,int v){
        if(deep[u]<deep[v]) swap(u,v);
        while(deep[u]>deep[v])
            u=ans[u][lg[deep[u]-deep[v]]];
        if(u==v) return u;
        for(int i=lg[deep[u]];i>=0;i--)
            if(ans[u][i]!=ans[v][i])
                u=ans[u][i],v=ans[v][i];
        return ans[u][0]; 
    }
    
    int Answer(int u,int v,int og,int fg,int l,int r,int k){
        if(l==r) return row[l];
        int sum=t[t[u].ls].si+t[t[v].ls].si-t[t[og].ls].si-t[t[fg].ls].si;
        int mid=(l+r)>>1;
        if(k<=sum) return Answer(t[u].ls,t[v].ls,t[og].ls,t[fg].ls,l,mid,k);
        return Answer(t[u].rs,t[v].rs,t[og].rs,t[fg].rs,mid+1,r,k-sum); 
    }
    
    int main(){
        pre_work();
        for(int i=1;i<=n;i++)
            if(from[i]==i) dfs(i,0,i);
        char ch[5];int x,y,k;
        for(int i=1;i<=TT;i++){
            scanf("%s",ch);x=in()^last;y=in()^last;
            if(ch[0]=='Q'){
                k=in()^last;
                int og=get_LCA(x,y),fg=ans[og][0];
                last=Answer(root[x],root[y],root[og],root[fg],1,tot,k);
                printf("%d\n",last);        
            }
            else{
                adds(x,y);adds(y,x);
                int fx=from[x],fy=from[y];
                if(size[fy]<size[fx]) dfs(y,x,fx);
                else dfs(x,y,fy);
            }
        }
        return 0;
    }