bzoj3123: [Sdoi2013]森林

题面在这里

题意：

给一个森林，森林有n个节点m条边。
现在有两种操作：
1.Q x y k 表示询问x-y这条链上点权的第k小。保证x，y在同一个连通块里。
2.L x y 表示链接x,y两点。保证x,y在不同的连通块里。
要求强制在线，last表示上一次的答案，每次x,y,k都要异或last.初始为0.

做法：

权值第k小想到主席树。（发现和上一题基本一样除了连接两个点的操作）
连接两个点其实就是把两棵树合并。
然后我们启发式合并，暴力地把小的树接到大的树上。
然后大概就没了。
另外这题一个坑的地方就是那个testcase是当前数据的测试点编号，不是数据组数！

代码：

/*************************************************************Problem: bzoj 3123 [Sdoi2013]森林User: fengyuanLanguage: C++Result: AcceptedTime: 12524 msMemory: 131972 kbSubmit_Time: 2018-01-08 14:33:42
*************************************************************/#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cctype>
#define mid (l+r>>1)
using namespace std;
typedef long long LL;inline LL read()
{char ch = getchar(); LL x = 0; int op = 1;for(; !isdigit(ch); ch = getchar()) if(ch == '-') op = -1;for(; isdigit(ch); ch = getchar()) x = x*10 + ch-'0';return x*op;
}
inline void write(LL a) { if(a < 0) putchar('-'); if(a >= 10) write(a/10); putchar(a%10+'0'); }const int N = 100010, M = 10000010;
int n, m, q, cnt, tot, all;
int head[N], p[N], rt[N], L[M], R[M], sum[M], depth[N], f[N][19], fa[N], sz[N], num[N], a[N];
char opt[5];
struct Edge{int to, nxt;Edge() {}Edge(int x, int y) { to = x, nxt = y; }
}e[N<<1];inline int getFa(int v) { return v == fa[v] ? v : fa[v] = getFa(fa[v]); }
inline void addEdge(int x, int y) { e[++ cnt] = Edge(y, head[x]); head[x] = cnt; }
inline void insert(int pre, int &rt, int l, int r, int x)
{rt = ++ all; sum[rt] = sum[pre]+1; L[rt] = L[pre]; R[rt] = R[pre];if(l == r) return;if(x <= mid) insert(L[pre], L[rt], l, mid, x);else insert(R[pre], R[rt], mid+1, r, x);
}
inline int query(int x, int y, int lca, int fa_lca, int l, int r, int k)
{if(l == r) return num[l];int lsum = sum[L[x]]+sum[L[y]]-sum[L[lca]]-sum[L[fa_lca]];if(lsum >= k) return query(L[x], L[y], L[lca], L[fa_lca], l, mid, k);else return query(R[x], R[y], R[lca], R[fa_lca], mid+1, r, k-lsum);
}
inline void dfs(int u, int lst, int s)
{depth[u] = s; f[u][0] = lst;for(int i = 1; i <= 17; i ++) f[u][i] = f[f[u][i-1]][i-1];insert(rt[lst], rt[u], 1, tot, a[u]);for(int i = head[u]; i; i = e[i].nxt) {int v = e[i].to; if(v == lst) continue;dfs(v, u, s+1);}
}
inline int LCA(int x, int y)
{if(depth[x] < depth[y]) swap(x, y);int tmp = depth[x] - depth[y];for(int i = 17; i >= 0; i --)if(tmp>>i&1) x = f[x][i];if(x == y) return x;for(int i = 17; i >= 0; i --)if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];return f[x][0];
}
int main()
{int Test = read();n = read(), m = read(), q = read(); cnt = 0; memset(head, 0, sizeof head);for(int i = 1; i <= n; i ++) a[i] = read(), num[i] = a[i];sort(num+1, num+1+n); tot = unique(num+1, num+1+n)-num-1;//p[i]是第i个数离散化后的编号for(int i = 1; i <= n; i ++) a[i] = lower_bound(num+1, num+1+tot, a[i])-num;for(int i = 1; i <= n; i ++) fa[i] = i, sz[i] = 1;for(int i = 1; i <= m; i ++) {int x = read(), y = read(), fx, fy;addEdge(x, y); addEdge(y, x);fx = getFa(x); fy = getFa(y);if(fx != fy) fa[fx] = fy, sz[fy] += sz[fx];}memset(depth, 0, sizeof depth); all = 0;memset(sum, 0, sizeof sum); memset(rt, 0, sizeof rt); memset(L, 0, sizeof L); memset(R, 0, sizeof R);memset(f, 0, sizeof f);for(int i = 1; i <= n; i ++) if(!depth[i]) { int rt = getFa(i); dfs(rt, 0, 1); }int lastans = 0;while(q --) {scanf("%s", opt);int x = read()^lastans, y = read()^lastans, k, z;z = LCA(x, y);if(opt[0] == 'Q') {k = read()^lastans; lastans = query(rt[x], rt[y], rt[z], rt[f[z][0]], 1, tot, k);write(lastans), puts("");} else {addEdge(x, y); addEdge(y, x);int fx = getFa(x), fy = getFa(y);if(sz[fx] > sz[fy]) swap(fx, fy), swap(x, y);fa[fx] = fy; sz[fy] += sz[fx];f[x][0] = y; dfs(x, y, depth[y]+1);//启发式合并}}return 0;
}