数据下载后对照无误
提交显示第一个点too short on line 1
//good luck
# include <iostream>
# include <cstdio>
# include <cmath>
# include <cstdlib>
# include <cstring>
# include <string>
# include <algorithm>
# include <vector>
# include <queue>
# include <ctime>
# include <map>
#define LL long long
#define maxn int(2e5+5)
#define is(a) (a>='0'&&a<='9')
#define iabs(a) ((a)>0?(a):(-a))
#define imax(a,b) ((a)>(b)?(a):(b))
#define imin(a,b) ((a)<(b)?(a):(b))
using namespace std;
struct data{int x,y,id;}a[maxn];
struct tree{int ls,rs,cnt;}t[maxn*200];
int N,M,T,n,mn,cache,testcase,lastans,st[maxn],fa[maxn][17],rt[maxn],size[maxn],deep[maxn];
int tot,hd[maxn],ver[maxn],nt[maxn];
inline void read(int &x)
{
x=0;bool f=0;char ch=getchar();
for (;!is(ch);ch=getchar()) f|=ch=='-';
for (;is(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
x=f?-x:x;
}
inline void addedge(int x,int y)
{
++tot; nt[tot] = hd[x]; ver[tot] = y; hd[x] = tot;
}
inline bool cmp1(data a,data b){return a.x<b.x;}
inline bool cmp2(data a,data b){return a.id<b.id;}
inline int getfa(int x)
{
int u = x;
for (int i = 16; i >= 0; --i)
{
if ((1<<i)&(deep[u]-1)) u=fa[u][i];
}
return u;
}
inline int lca(int x,int y)
{
if (deep[x]>deep[y]) swap(x,y);
for (int i = 16; i >= 0; --i)
{
if ((1<<i)&(deep[y]-deep[x])) y=fa[y][i];
}
if (x==y) return x;
for (int i = 16; i >= 0; --i)
{
if (fa[x][i]==fa[y][i]) continue;
x=fa[x][i]; y=fa[y][i];
}
return fa[x][0];
}
inline void up(int ro)
{
t[ro].cnt= t[t[ro].ls].cnt + t[t[ro].rs].cnt;
}
inline void Build(int L,int R)
{
int now=++n;
t[now].cnt=0;
if (L==R) {cache=n;return;}
int Mid=(L+R)>>1;
Build(L,Mid);
t[now].ls=cache;
Build(Mid+1,R);
t[now].rs=cache;
cache=now;
}
inline void update(int L,int R,int v,int x)
{
int now=++n;
int Mid=(L+R)>>1;
if (L==R) {t[n].cnt=t[v].cnt+1;return;}
if (x<=Mid)
{
t[now].rs=t[v].rs;
t[now].ls=n+1;
update(L,Mid,t[v].ls,x);
}
else
{
t[now].ls=t[v].ls;
t[now].rs=n+1;
update(Mid+1,R,t[v].rs,x);
}
up(now);
}
inline int dfs(int x,int y)
{
deep[x] = deep[y] + 1;
fa[x][0] = y;
for (int i = 1; i <= 16; ++i) fa[x][i] = fa[fa[x][i-1]][i-1];
rt[x]=n+1;
update(1,mn,rt[y],a[x].y);
for (int i = hd[x]; i ; i = nt[i])
{
int z = ver[i];
if (z==y) continue;
dfs(z,x);
}
}
inline int query(int L,int R,int u,int v,int l,int r,int k)
{
int Mid=(L+R)>>1;
if (L==R) return L;
if (t[t[u].ls].cnt+t[t[v].ls].cnt-t[t[l].ls].cnt-t[t[r].ls].cnt>=k) return query(L,Mid,t[u].ls,t[v].ls,t[l].ls,t[r].ls,k);
else return query(Mid+1,R,t[u].rs,t[v].rs,t[l].rs,t[r].rs,k-(t[t[u].ls].cnt+t[t[v].ls].cnt-t[t[l].ls].cnt-t[t[r].ls].cnt));
}
inline int Que(int x,int y,int k)
{
return query(1,mn,rt[x],rt[y],rt[lca(x,y)],rt[fa[lca(x,y)][0]],k);
}
int main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
read(testcase);
while (testcase--)
{
n=0; lastans=0; tot=0;
read(N); read(M); read(T);
for (int i = 1; i <= N; ++i) read(a[i].x),size[i]=1,a[i].id=i,deep[i]=1;
sort(a+1,a+1+N,cmp1);
for (int i = 1; i <= N; ++i)
a[i].y = ((i!=1)&&(a[i].x==a[i-1].x))?a[i-1].y:a[i-1].y+1,st[a[i].y]=a[i].x;
mn=a[N].y;
sort(a+1,a+1+N,cmp2);
for (int i = 1; i <= N; ++i)
for (int j = 0; j <= 16; ++j) fa[i][j] = 0;
rt[0]=1;
Build(1,mn);
for (int i = 1; i <= N; ++i)
{
rt[i]=n+1;
update(1,mn,1,a[i].y);
}
for (int i = 1; i <= M; ++i)
{
int x,y;
read(x); read(y);
int fx=getfa(x),fy=getfa(y);
if (size[fx]>size[fy]) swap(fx,fy),swap(x,y);
dfs(x,y);
addedge(x,y);
addedge(y,x);
size[fy]+=size[fx];
}
for (int i = 1; i <= T; ++i)
{
char ch; int x,y,k;
scanf("%c",&ch); read(x); read(y);
x^=lastans; y^=lastans;
if (ch=='Q')
{
read(k); k^=lastans;
lastans=st[Que(x,y,k)];
printf("%d\n",lastans);
}
if (ch=='L')
{
int fx=getfa(x),fy=getfa(y);
if (size[fx]>size[fy]) swap(fx,fy),swap(x,y);
dfs(x,y);
addedge(x,y);
addedge(y,x);
size[fy]+=size[fx];
}
}
for (int i = 1; i <= N; ++i) hd[i] = 0;
for (int i = 0 ; i <= tot; ++i) nt[i] = ver[i] = 0;
}
return 0;
}