【题解】P3224 [HNOI2012]永无乡
G我就是菜G
·
·
题解
Spaly+并查集
在原来平衡树的基础上，将 root 设为一个数组，root[i] 为第 i 个节点所在连通块的树根
$insert(y,x)$ 将 $x$ 节点插入到以 $y$ 为根的树下面，如果发现 $x,y$ 已经在同一个连通块里了（就是 $find(x)==find(y)$）就忽略该操作
然后接下来就是普通的 $splay$ 了
**注意：旋转的时候不要忘记更新 $root[x]$，查找时不要忘记返回 $-1$**
### 代码如下：
```cpp
#include <bits/stdc++.h>
#define N 4000010
using namespace std;
int size[N],t[N],fa[N],son[N][2],root[N];
int n,m,x,y,k,cnt;
char c;
void add(int x){t[++cnt]=x,size[cnt]=1;} //新建一个节点
void update(int x)
{
size[x]=size[son[x][0]]+size[son[x][1]]+1;
}
int whichson(int x)
{
return son[fa[x]][1]==x;
}
void rotate(int x)
{
int fat=fa[x],gfa=fa[fat];
int whichx=whichson(x),whichfa=whichson(fat);
fa[son[x][!whichx]]=fat;
son[fa[x]][whichx]=son[x][!whichx];
son[x][!whichx]=fat;
son[gfa][whichfa]=x;
fa[x]=gfa,fa[fat]=x;
update(fat),update(x);
}
void splay(int x,int y) //普通的splay
{
if (x==y) return;
int fat,gfa;
while (fa[x]!=y)
{
fat=fa[x],gfa=fa[fat];
if (gfa!=y)
if (whichson(x)==whichson(fat)) rotate(fat);
else rotate(x);
rotate(x);
}
if (!y) root[root[x]]=x,root[x]=x;
}
void insert(int i,int x,int fat)
{
if (!i)
{
son[fat][t[fat]<t[x]]=x;
fa[x]=fat;
return;
}
insert(son[i][t[i]<t[x]],x,i);
update(i);
}
int findnum(int now,int x)
{
if (now==0) return -1;
if (size[son[now][0]]+1==x) return now;
if (size[son[now][0]]>=x) return findnum(son[now][0],x);
else return findnum(son[now][1],x-size[son[now][0]]-1);
}
int find(int x)
{
return (root[x]==x) ? x : root[x]=find(root[x]);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&x),add(x); //每读入一个值就新开一个节点储存
for (int i=1;i<=n;i++)
root[i]=i; //初始化
for (int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
if (find(x)!=find(y))
{
splay(x,0);
insert(find(y),x,0);
root[x]=find(y); //别忘记更新 root[x] 值
splay(x,0); //每次splay(x,0)，保证其平衡
}
}
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
c=getchar();
while (c<'A'||c>'Z') c=getchar();
if (c=='Q')
{
scanf("%d%d",&x,&k);
printf("%d\n",findnum(find(x),k));
splay(x,0);
}
else
{
scanf("%d%d",&x,&y);
if (find(x)!=find(y))
{
splay(x,0);
insert(find(y),x,0);
root[x]=find(y);
splay(x,0);
}
}
}
return 0;
}
```