C++14(g++5.4) 解法, 执行用时: 480ms, 内存消耗: 111636K, 提交时间: 2020-09-28 19:48:52

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=8e4+10;
int fa[N][21],dep[N],head[N],cnt,tot,a[N],b[N],T[N],m,ffa[N],n,siz[N];
bool vis[N];
struct Tree{
    int l,r,sum;
}tree[N*500];
struct edge{
    int next,to;
}e[N<<1];
void add(int u,int v){
    e[++cnt].next=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
int LCA(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int i=20;i>=0;i--)
        if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
    if(u==v)return u;
    for(int i=20;i>=0;i--)
        if(fa[u][i]!=fa[v][i])
            u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
int build(int l,int r){
    int id=++tot;tree[id].sum=0;
    if(l==r)return id;
    int mid=l+r>>1;
    tree[id].l=build(l,mid);
    tree[id].r=build(mid+1,r);
    return id;
}
int update(int l,int r,int rt,int x){
    int id=++tot;tree[id]=tree[rt];
    if(l==r){tree[id].sum++;return id;}
    int mid=l+r>>1;
    if(x<=mid)tree[id].l=update(l,mid,tree[rt].l,x);
    else tree[id].r=update(mid+1,r,tree[rt].r,x);
    tree[id].sum=tree[tree[id].l].sum+tree[tree[id].r].sum;
    return id;
}
int query(int l,int r,int k,int u,int v,int lca1,int lca2){
    if(l==r)return b[l];
    int sum=tree[tree[u].l].sum+tree[tree[v].l].sum-tree[tree[lca1].l].sum-tree[tree[lca2].l].sum;
    int mid=l+r>>1;
    if(k<=sum)return query(l,mid,k,tree[u].l,tree[v].l,tree[lca1].l,tree[lca2].l);
    else return query(mid+1,r,k-sum,tree[u].r,tree[v].r,tree[lca1].r,tree[lca2].r);
}
void dfs(int u,int f){
    dep[u]=dep[f]+1;fa[u][0]=f;vis[u]=true;
    T[u]=update(1,m,T[f],a[u]);
    for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;if(v==f)continue;dfs(v,u);
    }
}
int _find(int x){return x==ffa[x]?x:ffa[x]=_find(ffa[x]);}
void _union(int &u,int &v){
    int x=_find(u),y=_find(v);
    if(siz[x]<siz[y])swap(x,y),swap(u,v);
    siz[x]+=siz[y];ffa[y]=x;
}
int main(){
    int t;scanf("%d",&t);scanf("%d",&n);int q1,q2;scanf("%d %d",&q1,&q2);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);m=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+m+1,a[i])-b,ffa[i]=i,siz[i]=1;
    for(int i=1;i<=q1;i++){
        int x,y;scanf("%d %d",&x,&y);_union(x,y);add(x,y);add(y,x);
    }
    T[0]=build(1,m);
    for(int i=1;i<=n;i++)
        if(!vis[i])
            dfs(_find(i),0);
    int ans=0;
    while(q2--){
        char op;scanf(" %c",&op);
        if(op=='Q'){
            int u,v,k;scanf("%d %d %d",&u,&v,&k);u^=ans,v^=ans,k^=ans;int lca=LCA(u,v);printf("%d\n",ans=query(1,m,k,T[u],T[v],T[lca],T[fa[lca][0]]));
        }else {
            int u,v;scanf("%d %d",&u,&v);u^=ans,v^=ans;_union(u,v);add(v,u);add(u,v);dfs(v,u);
        }
    }
}

C++ 解法, 执行用时: 550ms, 内存消耗: 108816K, 提交时间: 2022-01-27 14:53:02

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>

using namespace std;
const int maxn=1e5+5;

char op;
int a[maxn],b[maxn],n,m,q,mx,u,v,w,ans;
int dep[maxn],fa[maxn][18],lg[maxn],ft[maxn],sz[maxn];
int ls[maxn<<7],rs[maxn<<7],sum[maxn<<7],rt[maxn],now;
vector<int>ed[maxn];

int find(int x)
{
	return ft[x]==x?x:ft[x]=find(ft[x]);
}

void update(int u,int&v,int l,int r,int pos)
{
	v=++now,ls[v]=ls[u],rs[v]=rs[u],sum[v]=sum[u]+1;
	if(l==r)return;
	int mid=l+r>>1;
	if(pos<=mid)update(ls[u],ls[v],l,mid,pos);
	else update(rs[u],rs[v],mid+1,r,pos);
	return;
}

int query(int u1,int u2,int v1,int v2,int l,int r,int k)
{
	if(l==r)return b[l];
	int mid=l+r>>1,num=sum[ls[v1]]+sum[ls[v2]]-sum[ls[u1]]-sum[ls[u2]];
	if(num>=k)return query(ls[u1],ls[u2],ls[v1],ls[v2],l,mid,k);
	else return query(rs[u1],rs[u2],rs[v1],rs[v2],mid+1,r,k-num);
}

int LCA(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	while(dep[x]>dep[y])
	{
		x=fa[x][lg[dep[x]-dep[y]]-1];
	}
	if(x==y)return x;
	for(int i=17;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i],y=fa[y][i];
		}
	}
	return fa[x][0];
}

void dfs(int x,int f,int t)
{
	dep[x]=dep[f]+1,fa[x][0]=f,sz[t]++,ft[x]=t;
	update(rt[f],rt[x],1,mx,a[x]);
	for(int i=1;i<=17;i++)
	{
		fa[x][i]=fa[fa[x][i-1]][i-1];	
	}	
	for(auto y:ed[x])
	{
		if(y!=f)dfs(y,x,t);
	}
	return;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int T; cin>>T;
	for(int i=1;i<=1e5;i++)lg[i]=lg[i-1]+(!(i&i-1));
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i],ft[i]=i;
	sort(b+1,b+1+n); mx=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+mx,a[i])-b;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
		ed[u].push_back(v);
		ed[v].push_back(u);  
	}
	for(int i=1;i<=n;i++)if(ft[i]==i)dfs(i,0,i);
	for(int i=1;i<=q;i++)
	{
		cin>>op;
		if(op=='Q')
		{
			cin>>u>>v>>w;
			u^=ans,v^=ans,w^=ans;
			int lca=LCA(u,v);
			ans=query(rt[lca],rt[fa[lca][0]],rt[u],rt[v],1,mx,w);
			cout<<ans<<"\n";
		}
		else
		{
			cin>>u>>v;
			u^=ans,v^=ans;
			int x=find(u),y=find(v);
			if(sz[x]<sz[y])swap(x,y),swap(u,v);
			dfs(v,u,x),sz[y]=0;
			ed[v].push_back(u);
			ed[u].push_back(v);
		}
	}
	return 0;
}