小细节磕磕碰碰浪费了半个多小时的时间
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
对于每一个第一类操作，输出一个非负整数表示答案。
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、主席树启发式合并。
本来还想写个内存回收的，但是写完一来发现对效率好像不是很自信；二来看了看觉得空间也还过得去，就没再写回收了。
没有理解为什么森林初始不是全为点的。可能是为了区分我这样的大常数？
话说20s的题交上去刷新一下就返回TLE是什么机制……
#include<bits/stdc++.h>
const int maxn = ;
const int maxm = ;
const int maxNode = ; struct segNode
{
int l,r,val;
}a[maxNode];
struct Pool
{
int tot;
int newNode()
{
++tot, a[tot].l = a[tot].r = a[tot].val = ;
return tot;
}
}node;
char opt[];
int T,n,m,q,lastans;
int rt[maxn],c[maxn],tmp[maxn],fat[maxn],size[maxn];
int edgeTot,head[maxn],nxt[maxm],edges[maxm];
struct treeStruction
{
int fa[maxn][],dep[maxn];
void init()
{
memset(fa, , sizeof fa);
for (int i=; i<=n; i++) dep[i] = ;
}
int lca(int u, int v)
{
if (dep[u] < dep[v]) std::swap(u, v);
for (int i=; i>=; i--)
if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
if (u==v) return u;
for (int i=; i>=; i--)
if (fa[u][i]!=fa[v][i])
u = fa[u][i], v = fa[v][i];
return fa[u][];
}
}tre; int read()
{
char ch = getchar();
int num = , fl = ;
for (; !isdigit(ch); ch=getchar())
if (ch=='-') fl = -;
for (; isdigit(ch); ch=getchar())
num = (num<<)+(num<<)+ch-;
return num*fl;
}
int find(int x)
{
while (x!=fat[x]) x = fat[x];
return x;
}
void update(int &rt, int pre, int L, int R, int c)
{
rt = node.newNode();
a[rt] = a[pre], ++a[rt].val;
if (L==R) return;
int mid = (L+R)>>;
if (c <= mid) update(a[rt].l, a[pre].l, L, mid, c);
else update(a[rt].r, a[pre].r, mid+, R, c);
}
int query(int u, int v, int lca, int fa, int L, int R, int k)
{
if (L==R) return L;
int mid = (L+R)>>, val = a[a[u].l].val+a[a[v].l].val-a[a[lca].l].val-a[a[fa].l].val;
if (k <= val) return query(a[u].l, a[v].l, a[lca].l, a[fa].l, L, mid, k);
return query(a[u].r, a[v].r, a[lca].r, a[fa].r, mid+, R, k-val);
}
void connect(int x, int fat)
{
tre.dep[x] = tre.dep[fat]+, tre.fa[x][] = fat;
update(rt[x], rt[fat], , tmp[], c[x]);
for (int i=; i<=; i++)
tre.fa[x][i] = tre.fa[tre.fa[x][i-]][i-];
for (int i=head[x]; i!=-; i=nxt[i])
if (fat!=edges[i]) connect(edges[i], x);
}
void addedge(int u, int v)
{
int fu = find(u), fv = find(v);
if (size[fu] > size[fv]) std::swap(fu, fv), std::swap(u, v);
fat[fu] = fv, size[fv] += size[fu], connect(u, v);
edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot;
edges[++edgeTot] = u, nxt[edgeTot] = head[v], head[v] = edgeTot;
}
void discretization()
{
std::sort(tmp+, tmp+n+);
tmp[] = std::unique(tmp+, tmp+n+)-tmp-;
for (int i=; i<=n; i++)
{
c[i] = std::lower_bound(tmp+, tmp+tmp[]+, c[i])-tmp;
update(rt[i], , , tmp[], c[i]);
}
}
int main()
{
T = read();
memset(rt, , sizeof rt);
memset(head, -, sizeof head);
n = read(), m = read(), q = read();
tre.init();
node.tot = lastans = edgeTot = ;
for (int i=; i<=n; i++)
tmp[i] = c[i] = read(), fat[i] = i, size[i] = ;
discretization();
for (int i=; i<=m; i++) addedge(read(), read());
for (int i=; i<=q; i++)
{
scanf("%s",opt);
if (opt[]=='Q'){
int u = read()^lastans, v = read()^lastans;
int k = read()^lastans, lca = tre.lca(u, v);
lastans = tmp[query(rt[u], rt[v], rt[lca], rt[tre.fa[lca][]], , tmp[], k)];
printf("%d\n",lastans);
}else addedge(read()^lastans, read()^lastans);
}
return ;
}
END