数据下载后对照无误

提交显示第一个点too short on line 1

提交记录

code:

//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;
}