[sdoi2013] forest

Chairman tree on the tree + Heuristic merging

link ：[P3302 SDOI2013] The forest - Luogu | New ecology of computer science education (luogu.com.cn)

The question ： Given a forest , There are multiple operations , You can query x To y The second on the path k Small , You can also connect two trees into one .

Answer key ： First interval No k Small , Chairman tree maintenance . The third in the tree k The little empathy chairman tree , Select to inherit from the parent node when inheriting . Query at the same time 4 A little bit $x,y,lca,fa[lca]$. Now there are more connection operations , Due to the maximum number of connections n-1 After that, it finally becomes a tree , So consider heuristic merging , Each time we merge, we violently pull down the small trees and put them under the big trees , The average allocation complexity is log Level , Each point will rebuild the multiplier array, which is also complex log, The whole is revised to $O(nlo{g}^{2}n)$. Maintain the set of the lower tree with the union search set to facilitate the modification and calculation of the tree size .

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