3123: [Sdoi2013]森林
Time Limit: 20 Sec Memory Limit: 512 MB
Description
![[BZOJ3123][Sdoi2013]森林 主席树+启发式合并](https://image.miaokee.com:8440/aHR0cDovL3d3dy5seWRzeS5jb20vSnVkZ2VPbmxpbmUvdXBsb2FkLzIwMTMwNC8xKDMpLmpwZw%3D%3D.jpg?w=700 "[BZOJ3123][Sdoi2013]森林 主席树+启发式合并")
Input
第一行包含一个正整数testcase，表示当前测试数据的测试点编号。保证1≤testcase≤20。
第二行包含三个整数N，M，T，分别表示节点数、初始边数、操作数。第三行包含N个非负整数表示 N个节点上的权值。
接下来 M行，每行包含两个整数x和 y，表示初始的时候，点x和点y 之间有一条无向边, 接下来 T行，每行描述一个操作，格式为“Q x y k”或者“L x y ”，其含义见题目描述部分。
Output
对于每一个第一类操作，输出一个非负整数表示答案。
Sample Input
8 4 8
1 1 2 2 3 3 4 4
4 7
1 8
2 4
2 1
Q 8 7 3 Q 3 5 1
Q 10 0 0
L 5 4
L 3 2 L 0 7
Q 9 2 5 Q 6 1 6
Sample Output
2
1
4
2
HINT
对于第一个操作 Q 8 7 3，此时 lastans=0，所以真实操作为Q 8^0 7^0 3^0，也即Q 8 7 3。点8到点7的路径上一共有5个点，其权值为4 1 1 2 4。这些权值中，第三小的为 2，输出 2，lastans变为2。对于第二个操作 Q 3 5 1 ，此时lastans=2，所以真实操作为Q 3^2 5^2 1^2 ，也即Q 1 7 3。点1到点7的路径上一共有4个点，其权值为 1 1 2 4 。这些权值中，第三小的为2，输出2，lastans变为 2。之后的操作类似。
![[BZOJ3123][Sdoi2013]森林 主席树+启发式合并](https://image.miaokee.com:8440/aHR0cDovL3d3dy5seWRzeS5jb20vSnVkZ2VPbmxpbmUvdXBsb2FkLzIwMTMwNC8xKDQpLmpwZw%3D%3D.jpg?w=700 "[BZOJ3123][Sdoi2013]森林 主席树+启发式合并")
题解：
看到求k值，我们很容易想到主席树这种求区间k大值的工具（不了解树上主席树的同学可以看一下我之前的讲解http://www.cnblogs.com/LadyLex/p/7275164.html，再参考一下下面的代码）
但是，本题的合并操作给我们带来了麻烦，让我们无处下手。难道我们之间暴力添加吗？肯定会T。
所以我们考虑利用启发式合并，即把个数较小的树插入个数较大的树中。
启发式合并的操作听起来和暴力没有什么区别，但是它的复杂度是有保障的：
每次合并，新树的大小是原来较小树大小的二倍以上，因此最多需要logn次合并成了1棵树。
每次合并平均是(n/2)log权值的，因此总时间复杂度是O（nlognlog权值）的
如果离散化的话，跑的就更快了，大约O（nlog2n）（不过我自己的代码没有离散，233）
代码见下：
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N=,MAXN=;
int n,cnt,val[N],sum,adj[N],e;
int origin[N],belong[N],size[N],deep[N];
struct edge{int zhong,next;}s[N<<];
inline void swap(int &a,int &b){int t=a;a=b;b=t;}
inline void add(int qi,int zhong){s[++e].zhong=zhong;s[e].next=adj[qi];adj[qi]=e;}
int f[N][],bin[];
inline void mission1(int x)
{for(int i=;i<=;i++)f[x][i]=f[f[x][i-]][i-];}
inline int LCA(int a,int b)
{
if(deep[a]<deep[b])swap(a,b);
int cha=deep[a]-deep[b];
for(int j=;~j;j--)if(cha&bin[j])a=f[a][j];
if(a==b)return a;
for(int j=;~j;j--)
if(f[a][j]!=f[b][j])a=f[a][j],b=f[b][j];
return f[a][];
}
struct node
{
int cnt;node *ch[];
node(){cnt=;ch[]=ch[]=NULL;}
inline void update(){cnt=ch[]->cnt+ch[]->cnt;}
}*null=new node(),*root[N];
inline node* newnode()
{
node *o=new node();
o->ch[]=o->ch[]=null;
return o;
}
inline int query(int x,int y,int k)
{
int lca=LCA(x,y),t=f[lca][],l=,r=MAXN;
node *a=root[x],*b=root[y],*c=root[lca],*d=root[t];
while(l<r)
{
int tmp=a->ch[]->cnt+b->ch[]->cnt-c->ch[]->cnt-d->ch[]->cnt,mi=(l+r)>>;
if(tmp>=k)a=a->ch[],b=b->ch[],c=c->ch[],d=d->ch[],r=mi;
else k-=tmp,a=a->ch[],b=b->ch[],c=c->ch[],d=d->ch[],l=mi+;
}
return r;
}
void insert(node *&a,node *b,int l,int r,int pos)
{
a->cnt=b->cnt+;
int mi=(l+r)>>;
if(l==r)return;
if(pos<=mi)a->ch[]=b->ch[],a->ch[]=newnode(),insert(a->ch[],b->ch[],l,mi,pos);
else a->ch[]=b->ch[],a->ch[]=newnode(),insert(a->ch[],b->ch[],mi+,r,pos);
a->update();
}
void dfs1(int rt,int fa)
{
f[rt][]=fa;mission1(rt);
sum++;deep[rt]=deep[fa]+;belong[rt]=cnt;
insert(root[rt],root[fa],,MAXN,val[rt]);
for(int i=adj[rt];i;i=s[i].next)
if(s[i].zhong!=fa)dfs1(s[i].zhong,rt);
}
void dfs2(int rt,int fa,int anc)
{
f[rt][]=fa;deep[rt]=deep[fa]+;mission1(rt);belong[rt]=anc;
insert(root[rt],root[fa],,MAXN,val[rt]);
for(int i=adj[rt];i;i=s[i].next)
if(s[i].zhong!=fa)dfs2(s[i].zhong,rt,anc);
}
int main()
{
null->ch[]=null->ch[]=null;
bin[]=;for(int i=;i<=;i++)bin[i]=bin[i-]<<;
int ans=,m,t,a,b,d;char c[];scanf("%d",&t);
scanf("%d%d%d",&n,&m,&t);
for(int i=;i<=n;i++)root[i]=newnode();
for(int i=;i<=n;i++)scanf("%d",&val[i]);
while(m--)scanf("%d%d",&a,&b),add(a,b),add(b,a);
for(int i=;i<=n;i++)
if(!belong[i])sum=,cnt++,dfs1(i,),origin[cnt]=i,size[cnt]=sum;
while(t--)
{
scanf("%s%d%d",c,&a,&b);a^=ans,b^=ans;
if(c[]=='Q')scanf("%d",&d),d^=ans,printf("%d\n",ans=query(a,b,d));
else
{
add(a,b),add(b,a);
if(size[belong[a]]>size[belong[b]])
size[belong[a]]+=size[belong[b]],dfs2(b,a,belong[a]);
else size[belong[b]]+=size[belong[a]],dfs2(a,b,belong[b]);
}
}
}