【BZOJ3123】[SDOI2013] 森林（启发式合并主席树）

点此看题面

大致题意： 给你一片森林，有两种操作：询问两点之间的第\(k\)小点权和在两棵树之间连一条边。

前置技能：树上主席树

做这道题目，我们首先要会树上主席树。

关于树上主席树，这有一道很好的例题：【洛谷2633】Count on a tree（只包含此题的询问操作）。

接下来，我们就将询问操作略过不提了（毕竟在这道题目中已经介绍过了），而主要讲讲如何连边。

启发式合并主席树

对于连边操作，我们需要启发式合并主席树（当然，也有一些奆佬是用\(LCT\)的）。

关于启发式合并的时间复杂度证明，我写过一篇很烂的博客，可以去看一下（其实它与按秩合并是同一个东西）。

如果要将两棵主席树合并，我们一般选择将深度小的主席树合并到深度大的主席树上。

千万注意，比较的是深度而不是子树大小！不然会像我一样\(T\)飞。

至于为什么比较深度，在此摘录\(hl666\)神犇的原话如下：

哦，对了，还没有讲怎么合并。

其实也非常简单，直接对深度较小的主席树重新扫一遍进行更新即可（具体操作见代码吧）。

代码

#include<bits/stdc++.h>

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)<(y)?(x):(y))

#define uint unsigned int

#define LL long long

#define ull unsigned long long

#define swap(x,y) (x^=y,y^=x,x^=y)

#define abs(x) ((x)<0?-(x):(x))

#define INF 1e9

#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))

#define ten(x) (((x)<<3)+((x)<<1))

#define N 80000

#define LogN 20

#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)

using namespace std;

int n,m,cnt,ee=0,a[N+5],p[N+5],lnk[N+5],Depth[N+5],fa[N+5][LogN+5];

struct edge

{

    int to,nxt;

}e[(N<<1)+5];

class FIO

{

    private:

        #define Fsize 100000

        #define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)

        #define pc(ch) (FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,FoutSize,stdout),Fout[(FoutSize=0)++]=ch))

        int f,FoutSize,OutputTop;char ch,Fin[Fsize],*FinNow,*FinEnd,Fout[Fsize],OutputStack[Fsize];

    public:

        FIO() {FinNow=FinEnd=Fin;}

        inline void read(int &x) {x=0,f=1;while(!isdigit(ch=tc())) f=ch^'-'?1:-1;while(x=ten(x)+(ch&15),isdigit(ch=tc()));x*=f;}

        inline void read_char(char &x) {while(isspace(x=tc()));}

        inline void read_string(string &x) {x="";while(isspace(ch=tc()));while(x+=ch,!isspace(ch=tc())) if(!~ch) return;}

        inline void write(int x) {if(!x) return (void)pc('0');if(x<0) pc('-'),x=-x;while(x) OutputStack[++OutputTop]=x%10+48,x/=10;while(OutputTop) pc(OutputStack[OutputTop]),--OutputTop;}

        inline void write_char(char x) {pc(x);}

        inline void write_string(string x) {register int i,len=x.length();for(i=0;i<len;++i) pc(x[i]);}

        inline void end() {fwrite(Fout,1,FoutSize,stdout);}

}F;

inline int LCA(int x,int y)//倍增LCA

{

    register int i;

    if(Depth[x]<Depth[y]) swap(x,y);

    for(i=0;Depth[x]^Depth[y];++i) if((Depth[x]^Depth[y])&(1<<i)) x=fa[x][i];

    if(!(x^y)) return x;

    for(i=0;fa[x][i]^fa[y][i];++i);

    for(--i;i>=0;--i) if(fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];

    return fa[x][0];

}

inline int GetRt(int x)//求出x所在树的根

{

    register int i;

    for(i=0;Depth[x];++i) if(Depth[x]&(1<<i)) x=fa[x][i];

    return x;

}

class Class_ChairmanTree//主席树

{

    private:

        int n,tot,Root[N+5];

        struct Tree

        {

            int Val,Size,Level,Son[2];

        }node[N*LogN<<4];

        inline void Build(int l,int r,int &rt)//建树

        {

            if(!rt&&(rt=++tot),!(l^r)) return;

            register int mid=l+r>>1;

            Build(l,mid,node[rt].Son[0]),Build(mid+1,r,node[rt].Son[1]);

        }

        inline void ins(int l,int r,int &rt,int lst,int val)//插入

        {

            if(node[rt=++tot]=node[lst],++node[rt].Size,!(l^r)) return;

            register int mid=l+r>>1;

            val<=mid?ins(l,mid,node[rt].Son[0],node[lst].Son[0],val):ins(mid+1,r,node[rt].Son[1],node[lst].Son[1],val);

        }

        inline int qry(int l,int r,int rt1,int rt2,int rt3,int rt4,int k)//询问

        {

            if(!(l^r)) return l;

            register int mid=l+r>>1,t=node[node[rt3].Son[0]].Size+node[node[rt4].Son[0]].Size-node[node[rt1].Son[0]].Size-node[node[rt2].Son[0]].Size;

            if(t>=k) return qry(l,mid,node[rt1].Son[0],node[rt2].Son[0],node[rt3].Son[0],node[rt4].Son[0],k);

            else return qry(mid+1,r,node[rt1].Son[1],node[rt2].Son[1],node[rt3].Son[1],node[rt4].Son[1],k-t);

        }

    public:

        inline void Init(int len) {Build(1,n=len,Root[0]);}//初始化

        inline void Insert(int v,int nv,int val) {ins(1,n,Root[nv],Root[v],val);}

        inline int Query(int v1,int v2,int k) {return qry(1,n,Root[LCA(v1,v2)],Root[fa[LCA(v1,v2)][0]],Root[v1],Root[v2],k);}

        inline bool Smaller(int rt1,int rt2) {return node[rt1].Level<node[rt2].Level;}//判断rt1所在树的深度是否小于rt2所在树的深度

        inline void AddLevel(int rt) {++node[rt].Level;}//将rt所在树的深度加1

}ChairmanTree;

inline int find(int x)//离散化

{

    register int l=1,r=cnt,mid=l+r>>1;

    for(;l<=r;mid=l+r>>1) p[mid]<x?l=mid+1:r=mid-1;

    return l;

}

inline void Init(int x)//初始化

{

    register int i;

    for(ChairmanTree.Insert(fa[x][0],x,find(a[x])),i=1;i<=LogN;++i) fa[x][i]=fa[fa[x][i-1]][i-1];

    for(i=lnk[x];i;i=e[i].nxt) if(fa[x][0]^e[i].to) Depth[e[i].to]=Depth[x]+1,fa[e[i].to][0]=x,Init(e[i].to);

}

int main()

{

    register int i,x,y,z,fx,fy,Q,ans=0;register char op;

    for(F.read(n),F.read(n),F.read(m),F.read(Q),i=1;i<=n;++i) F.read(a[i]),p[i]=a[i];

    for(i=1;i<=m;++i) F.read(x),F.read(y),add(x,y),add(y,x);

    for(sort(p+1,p+n+1),ChairmanTree.Init(cnt=unique(p+1,p+n+1)-p-1),i=1;i<=n;++i) if(!fa[i][0]) Init(i);

    while(Q--)

    {

    	F.read_char(op),F.read(x),F.read(y);

        if(op^'L') F.read(z),F.write(ans=p[ChairmanTree.Query(x^ans,y^ans,z^ans)]),F.write_char('\n');

        else

        {

            fx=GetRt(x^=ans),fy=GetRt(y^=ans),add(x,y),add(y,x);//记得连边

            if(ChairmanTree.Smaller(fx,fy)) swap(fx,fy),swap(x,y);//比较深度，选择深度较小的树合并到深度较大的树上

            ChairmanTree.AddLevel(fx),fa[y][0]=x,Depth[y]=Depth[x]+1,Init(y);//重新建树

        }

    }

    return F.end(),0;

}