bzoj 3123 [Sdoi2013]森林（主席树，lca，启发式合并）

Description

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

1
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
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。之后的操作类似。

【思路】

主席树+倍增lca+启发式合并

如果没有连边操作的话就是luo主席树。两棵树要相连，那一棵在上面无所谓，因为我们要遍历处于下方的树的所有节点所以我们采用启发式合并，即每次选择结点数更小的树放在下面，然后重建每一个结点。

【代码】

  1 #include<cmath>
  2 #include<queue>
  3 #include<vector>
  4 #include<cstdio>
  5 #include<cstring>
  6 #include<iostream>
  7 #include<algorithm>
  8 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)
  9 using namespace std;
 10 
 11 const int N = 100002;
 12 const int M = 400*N;
 13 const int D = 17;
 14 
 15 struct Tnode {
 16     int sum,lc,rc;
 17 } T[M];
 18 
 19 int n,m,q,sz,rt[N];
 20 int p[N],siz[N];
 21 int fa[N][D],hash[N],dep[N];
 22 int v[N],tot;
 23 vector<int> g[N];
 24 
 25 void read(int& x) {
 26     char c=getchar();
 27     int f=1;x=0;
 28     while(!isdigit(c)) {
 29         if(c=='-') f=-1; c=getchar();
 30     }
 31     while(isdigit(c))
 32         x=x*10+c-'0',c=getchar();
 33     x*=f;
 34 }
 35 
 36 int ifind(int u)
 37 {
 38     while(fa[u][0]) u=fa[u][0];
 39     return u;
 40 }
 41 void insert(int l,int r,int x,int& y,int num)
 42 {
 43     T[y=++sz]=T[x]; T[y].sum++;
 44     if(l==r) return ;
 45     int mid=(l+r)>>1;
 46     if(num<=mid) insert(l,mid,T[x].lc,T[y].lc,num);
 47     else insert(mid+1,r,T[x].rc,T[y].rc,num);
 48 }
 49 void dfs(int u,int f)
 50 {
 51     dep[u]=dep[f]+1; fa[u][0]=f; siz[u]=1;
 52     insert(1,tot,rt[f],rt[u],v[u]);
 53     FOR(i,1,D-1)                                                        //p1
 54         fa[u][i]=fa[fa[u][i-1]][i-1];
 55     FOR(i,0,(int)g[u].size()-1) {
 56         int v=g[u][i];
 57         if(v!=f) {
 58             dfs(v,u);
 59             siz[u]+=siz[v];
 60         }
 61     }
 62 }
 63 int lca(int u,int v)
 64 {
 65     if(dep[u]<dep[v]) swap(u,v);
 66     int t=dep[u]-dep[v];
 67     FOR(j,0,D-1)
 68         if(t&(1<<j)) u=fa[u][j];
 69     if(u==v) return u;
 70     for(int j=D-1;j>=0;j--)
 71         if(fa[u][j]!=fa[v][j]) u=fa[u][j],v=fa[v][j];
 72     return fa[u][0];
 73 }
 74 int query(int l,int r,int a,int b,int c,int d,int rk)
 75 {
 76     if(l==r) return l;
 77     int mid=(l+r)>>1;
 78     int now=T[T[a].lc].sum+T[T[b].lc].sum-T[T[c].lc].sum-T[T[d].lc].sum;
 79     if(rk<=now) return query(l,mid,T[a].lc,T[b].lc,T[c].lc,T[d].lc,rk);
 80     else return query(mid+1,r,T[a].rc,T[b].rc,T[c].rc,T[d].rc,rk-now);
 81 }
 82 int query(int x,int y,int z)
 83 {
 84     int c=lca(x,y);
 85     return query(1,tot,rt[x],rt[y],rt[c],rt[fa[c][0]],z);
 86 }
 87 
 88 int main()
 89 {
 90         int kase; read(kase);
 91         read(n),read(m),read(q);
 92         FOR(i,1,n) {
 93             read(v[i]); hash[i]=v[i];
 94             fa[i][0]=0;
 95         }
 96         sort(hash+1,hash+n+1);
 97         tot=unique(hash+1,hash+n+1)-hash-1;
 98         FOR(i,1,n)
 99             v[i]=lower_bound(hash+1,hash+tot+1,v[i])-hash;
100         char op[5];
101         int ans=0,x,y,z;
102         FOR(i,1,m) {
103             read(x),read(y);
104             g[x].push_back(y);
105             g[y].push_back(x);
106         }
107         FOR(i,1,n) if(!fa[i][0]) dfs(i,0);
108         FOR(i,1,q) {
109             scanf("%s",op);
110             read(x),read(y);
111             x^=ans; y^=ans;
112             if(op[0]=='Q') {
113                 read(z);
114                 z^=ans;
115                 printf("%d
",ans=hash[query(x,y,z)]);
116             } else {
117                 int fx=ifind(x),fy=ifind(y);
118                 if(siz[fx]<siz[fy])
119                         swap(fx,fy),swap(x,y);
120                 siz[fx]+=siz[fy];
121                 g[x].push_back(y);
122                 g[y].push_back(x);
123                 dfs(y,x);
124             }
125         }
126         return 0;
127 }