永无乡solution
(尚未讲解)
前置技能：并查集及其“代表”思想；权值线段树（会讲解）；权值线段树上二分求k-th（会讲解）；动态开点（会讲解）;线段树合并(会讲解)
PS1：此题是有平衡树的解法的，但其实麻烦了（其实是我不太会）
PS2：如果你不会并查集，那你有必要先去学一下
先关注“联通”二字，即要维护图上的联通性。而并查集非常适合解决此类问题。
由此，我们得到一个暴力做法：
对于合并操作，直接在并查集上合并x,y即可，每次$O(1)$；
对于查询操作，直接找出所有与x同一集合的点，按重要度排序后第k小即为所求，最坏每次$O(nlogn)$;
总时间复杂度最坏$O(q\times nlogn)$。
看到查询居然要最坏每次$O(nlogn)$的复杂度，有很大的优化空间。
如何动态求k-th?
如果您想到了平衡树,那么您就已经可以解决此题了,不用继续往下了.
而如果您不是很会平衡树:
权值线段树也能(通过线段树上二分)$O(logn)$动态维护k-th可以参见这里
也就是说,我们要查询与x联通的点里面第k重要的,就可以这样实现$O(logn)$的查询
但这样有两个问题:
1. 空间开销大.对于每个点都开一个大小为$O(n)$的线段树,总空间复杂度$O(n^2)$,无法承受.考虑到每次询问实际用到的点仅$O(logn)$个,总共也就最多访问$O(qlogn)$个节点,使用动态开点 (没错,还是同一篇blog),将空间降为$O(min(n^2,qlogn))$
2. 每次合并x,y时,要将与其联通的所有点都插入它们,每次最坏甚至可能超越$O(n)$.考虑并查集的”代表”思想:设sgt(i)表示与点i联通的点构成的线段树,由于联通是双向的,有:$$sgt(x)=sgt(y)\ if(x,y联通)$$也就是说,在并查集上合并(x,y)的同时,把sgt(x)也与sgt(y)合并,查询时在find(x)上查询.
这带来了新的问题:普通的合并,复杂度不会低于$O(n)$.可以使用启发式合并,这样大概是两个log.但更优的做法是使用线段树合并
权值线段树的线段树合并代码大概是这样的:
typedef long long ll;
typedef unsigned un;
ll uni(ll a,ll b,un l=1,un r=n)//把sgt(a)合并到sgt(b)上,并返回合并后点的编号
{
if(!a)return b;//有一个为空,返回
if(!b)return a;
if(l==r)//叶子节点,直接合并
{
t[b].v+=t[a].v;
return b;
}
un mid=(l+r)>>1;
t[b].ls=uni(t[a].ls,t[b].ls,l,mid);//递归合并子节点
t[b].rs=uni(t[a].rs,t[b].rs,mid+1,r);
pushup(b);//更新当前点
return b;
}
每个点至多被合并一次,总复杂度$O((m+q)logn)$
再讲解一下几个细节:初始化并查集;每个点先把自己的重要度插入自己的线段树里;合并的时候都是对find(x),find(y)进行合并;
最后,总时间复杂度$O((n+m+q)logn)$,空间复杂度$O(min(n^2,qlogn))$
//Wan Hong 3.0
//notebook
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include <cmath>
typedef int ll;//long long makes MLE.
typedef unsigned un;
typedef std::pair<ll,ll> pll;
typedef std::string str;
#define INF (1ll<<58)
ll read()
{
ll f=1,x=0;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
bool umax(ll& a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
bool umin(ll& a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
/**********/
#define MAXN 300011
struct ufs//Union_Find_Set
{
ll fa[MAXN];
void build(ll n)
{
for(ll i=1;i<=n;++i)fa[i]=i;
}
ll find(ll x)
{
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
void uni(ll u,ll v)
{
u=find(u),v=find(v);
fa[u]=v;
}
}s;
ll n,m,q;
struct node//线段树的节点(动态开点的)
{
ll v,ls,rs;
node()
{
v=ls=rs=0;
}
node(ll _v,ll _ls,ll _rs)
{
v=_v,ls=_ls,rs=_rs;
}
}t[MAXN*18+1];
ll cnt=0;
void pushup(un num)
{
t[num].v=t[t[num].ls].v+t[t[num].rs].v;
}
void modify(ll x,ll k,un num,un l=1,un r=n)在sgt(num)上将x的出现次数加上k
{
if(l==r)
{
if(l==x)t[num].v+=k;
return;
}
un mid=(l+r)>>1;
if(x<=mid)
{
if(!t[num].ls)t[num].ls=++cnt;//动态开点
modify(x,k,t[num].ls,l,mid);
}
else
{
if(!t[num].rs)t[num].rs=++cnt;
modify(x,k,t[num].rs,mid+1,r);
}
pushup(num);
}
ll uni(ll a,ll b,un l=1,un r=n)//线段树合并
{
if(!a)return b;
if(!b)return a;
if(l==r)
{
t[b].v+=t[a].v;
return b;
}
un mid=(l+r)>>1;
t[b].ls=uni(t[a].ls,t[b].ls,l,mid);
t[b].rs=uni(t[a].rs,t[b].rs,mid+1,r);
pushup(b);
return b;
}
ll Qkth(ll k,un num,un l=1,un r=n)//权值线段树上求k-th
{
if(l==r)return l;
un mid=(l+r)>>1;
if(k<=t[t[num].ls].v)return Qkth(k,t[num].ls,l,mid);
else return Qkth(k-t[t[num].ls].v,t[num].rs,mid+1,r);
}
ll v[MAXN],num[MAXN];//重要度排名;重要度排名所对应的点的编号
//main内有一些debug语句,忽略即可
int main()
{
//freopen("out.out","w",stdout);
n=read(),m=read();
s.build(n);
cnt=n;//我这里用了一个技巧,把i表示的线段树的编号就设为i
for(ll i=1;i<=n;++i)
{
v[i]=read();
num[v[i]]=i;
modify(v[i],1,i);//插入自己的重要度
}
for(ll i=1;i<=m;++i)
{
ll a=s.find(read()),b=s.find(read());//合并的是并查集上的根节点
if(a==b)continue;//同一集合内不用合并
s.uni(a,b);//并查集上合并
uni(a,b);//线段树上合并
}
q=read();
for(ll i=1;i<=q;++i)
{
char op=getchar();
while(op!='B'&&op!='Q')op=getchar();
//printf("task %d:",i);
if(op=='B')
{
ll a=s.find(read()),b=s.find(read());
//printf("a=%d,size=%d;b=%d,size=%d\n",a,t[a].v,b,t[b].v);
if(a==b)continue;//同一集合内不用合并
s.uni(a,b);//并查集上合并
uni(a,b);//线段树上合并
//printf("unisize=%d\n",t[b].v);
}
else
{
ll a=s.find(read()),k=read();//权值线段树上求k-th
//printf("Query %d,size=%d\n",a,t[a].v);
if(k>t[a].v)printf("-1\n");
else printf("%d\n",num[Qkth(k,a)]);
}
//printf("pass %lld...\n",i);
}
return 0;
}
