这题和 COT1 一定有 JQ 喵~
线段树的启发式合并，每次要连接两个点时就对比较小的那棵树暴力 DFS 一边
然后均摊时间依旧是 logn 的，均摊真是世界上最邪恶的东西了……
然后这题的数据是要卖萌么？！
testcase 的存在意义是被阿卡林噎掉了么？！
#include <cstdio>
#include <cstring>
#include <algorithm>
const int sizeOfPoint=;
const int sizeOfEdge=;
const int sizeOfNode=; inline int lg(int);
inline void swap(int & , int & );
inline char getch();
inline int getint();
inline void putint(int); struct edge {int point; edge * next;};
edge memory_edge[sizeOfEdge], * port_edge=memory_edge;
inline edge * newedge(int, edge * );
inline void link(int, int); struct node {int c; node * l , * r; inline node();};
node * null=new node();
node memory_node[sizeOfNode], * port_node=memory_node;
inline node * newnode(node * =null);
node * insert(node * , int, int, int); int b[sizeOfPoint], s[sizeOfPoint];
int find(int);
inline void merge(int, int); int testcase;
int N, M, T, U;
int p[sizeOfPoint], q[sizeOfPoint];
int f[sizeOfPoint], d[sizeOfPoint], a[][sizeOfPoint];
edge * e[sizeOfPoint];
node * t[sizeOfPoint];
inline void clear();
inline bool cmp(int, int);
inline void discretization();
void dfs(int);
inline int lca(int, int);
inline int query(int, int, int); int main()
{
int lastans=; testcase=getint();
for (testcase=;testcase;testcase--)
{
N=getint(), M=getint(), T=getint();
clear();
for (int i=;i<=N;i++)
p[i]=getint();
for (int i=;i<=M;i++)
{
int u=getint(), v=getint();
link(u, v);
}
discretization(); for (int i=;i<=N;i++) if (f[i]==-)
{
f[i]=; d[i]=;
dfs(i);
} for (int i=;i<=T;i++)
{
char c=getch(); int x=getint()^lastans, y=getint()^lastans;
if (c=='Q')
{
int k=getint()^lastans;
lastans=query(x, y, k);
putint(lastans);
}
else
{
int bx=find(x), by=find(y);
if (bx==by) continue;
if (s[bx]<s[by]) swap(x, y);
link(x, y);
f[y]=x; d[y]=d[x]+;
dfs(y);
}
}
} return ;
} inline int lg(int x)
{
return -__builtin_clz(x);
}
inline void swap(int & x, int & y)
{
int z=x;
x=y;
y=z;
}
inline char getch()
{
register char ch;
do ch=getchar(); while (ch!='L' && ch!='Q');
return ch;
}
inline int getint()
{
register int num=;
register char ch=, last;
do last=ch, ch=getchar(); while (ch<'' || ch>'');
do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');
if (last=='-') num=-num;
return num;
}
inline void putint(int num)
{
char stack[];
register int top=;
if (num==) stack[top=]='';
if (num<) putchar('-'), num=-num;
for ( ;num;num/=) stack[++top]=num%+'';
for ( ;top;top--) putchar(stack[top]);
putchar('\n');
} inline edge * newedge(int point, edge * next)
{
edge * ret=port_edge++;
ret->point=point; ret->next=next;
return ret;
}
inline void link(int u, int v)
{
e[u]=newedge(v, e[u]);
e[v]=newedge(u, e[v]);
merge(u, v);
} inline node::node()
{
this->c=;
this->l=this;
this->r=this;
}
inline node * newnode(node * t)
{
node * newt=port_node++;
*newt=*t;
return newt;
}
node * insert(node * t, int l, int r, int k)
{
t=newnode(t);
t->c++;
if (l==r) return t; int m=(l+r)>>;
if (k<=m) t->l=insert(t->l, l, m, k);
else t->r=insert(t->r, m+, r, k);
return t;
} int find(int u)
{
return !b[u]?u:b[u]=find(b[u]);
}
inline void merge(int u, int v)
{
u=find(u); v=find(v);
b[v]=u; s[u]+=s[v];
} inline void clear()
{
port_edge=memory_edge;
memset(e, , sizeof(e));
port_node=memory_node;
for (int i=;i<=N;i++) t[i]=null;
memset(f, -, sizeof(f));
memset(d, -, sizeof(d));
memset(b, , sizeof(b));
memset(a, , sizeof(a));
for (int i=;i<=N;i++) s[i]=;
}
inline bool cmp(int a, int b)
{
return p[a]<p[b];
}
inline void discretization()
{
static int k[sizeOfPoint]; for (int i=;i<=N;i++) k[i]=i;
std::sort(k+, k+N+, cmp); q[U=]=p[k[]]; p[k[]]=;
for (int i=;i<=N;i++)
{
if (p[k[i]]>q[U]) q[++U]=p[k[i]];
p[k[i]]=U;
}
}
void dfs(int u)
{
t[u]=insert(t[f[u]], , U, p[u]);
if (d[u]>)
{
int lim=lg(d[u]);
a[][u]=f[u];
for (int i=;i<=lim;i++)
a[i][u]=a[i-][a[i-][u]];
for (int i=lim+;i<;i++)
a[i][u]=;
} for (edge * i=e[u];i;i=i->next) if (i->point!=f[u])
{
f[i->point]=u;
d[i->point]=d[u]+;
dfs(i->point);
}
}
inline int lca(int u, int v)
{
if (d[u]<d[v]) swap(u, v);
while (int dist=d[u]-d[v]) u=a[__builtin_ctz(dist)][u];
if (u==v) return u;
for (int i=;i>=;i--)
if (a[i][u]!=a[i][v])
u=a[i][u],
v=a[i][v];
return f[u];
}
inline int query(int a, int b, int k)
{
int c=lca(a, b), d=f[c];
node * ta=t[a], * tb=t[b], * tc=t[c], * td=t[d];
int l=, r=U, m; for ( ;l<r; )
{
m=(l+r)>>;
if (ta->l->c+tb->l->c-tc->l->c-td->l->c>=k)
{
ta=ta->l; tb=tb->l; tc=tc->l; td=td->l;
r=m;
}
else
{
k-=ta->l->c+tb->l->c-tc->l->c-td->l->c;
ta=ta->r; tb=tb->r; tc=tc->r; td=td->r;
l=m+;
}
} return q[l];
}
又 R 又 T 一时爽