题解：AT_abc395_d [ABC395D] Pigeon Swap
Revitalize
·
·
题解
赛时糊的抽象做法。
题面
有 N 只标有 1, 2, \ldots, N 的鸽子和 N 个标有 1, 2, \ldots, N 的鸽巢。
最初，鸽子 i 在 (1 \leq i \leq N) 巢中。 (1 \leq i \leq N) 在巢 i 中。
- 给定整数 $a$ 和 $b$ 。 $(1 \leq a \leq N, 1 \leq b \leq N)$ .将鸽子 $a$ 从当前巢中取出，移到巢 $b$ 中。
- 给你整数 $a$ 和 $b$ 。 $(1 \leq a,b \leq N)$ .将巢 $a$ 中的所有鸽子移动到巢 $b$ ，并将巢 $b$ 中的所有鸽子移动到巢 $a$ 。这两次移动是同时进行的。
- 给你一个整数 $a$ $(1 \leq a \leq N)$ ，输出鸽子 $a$ 所在的巢的编号。
### 解法
考虑对于每个巢，维护一个什么结构，那么它应该满足插入一个数，删除一个数，且两个结构可以迅速互换。
平衡树显然可以。
所以就可以开 $N$ 棵平衡树。
每棵平衡树中，再定义一个 $rt$ 的父亲 $id$，表示这棵平衡树所代表的巢的序号。
操作一就是插入操作加删除操作，复杂度均摊 $O(\log n)$。
操作三就是从 $a$ 开始一直向上跳到它所在的平衡树的 $id$，返回，复杂度均摊 $O(\log n)$。
操作二就是让两棵平衡树的 $rt$ 互换父亲，复杂度 $O(1)$。
总复杂度 $O(q\log n)$。
因为 FHQ Treap 不记录 $fa$，所以用 Splay。（太菜了只会这两种）
在 Splay 时旋到这棵树 $id$ 的下面就可以了。
插入的时候就以节点编号作为关键字在树上插入即可。
最后 $id$ 所对应的节点因为是巢的编号，所以要与鸽子节点区分开，所以不妨令 $i+n$ 号节点代表 $i$ 号巢。
### 代码
压行严重，不喜勿喷。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Opshacom{
const int N=3e6+5;
int fa[N],ch[N][2],n,q;
inline int getrt(int x){while(1){if(fa[x]>n)return x; x=fa[x];}}
inline bool get(int x){return (x==ch[fa[x]][1]);}
inline void rotate(int x){
int f=fa[x],gf=fa[f],lr=get(x);
ch[f][lr]=ch[x][lr^1];
if(ch[x][lr^1]) fa[ch[x][lr^1]]=f;
ch[x][lr^1]=f,fa[f]=x,fa[x]=gf;
if(gf) ch[gf][f==ch[gf][1]]=x;
}
inline void splay(int x){
int goal=fa[getrt(x)];
while(fa[x]!=goal){
int f=fa[x],g=fa[fa[x]];
if(g!=goal){if(get(f)==get(x)) rotate(f);else rotate(x);}
rotate(x);
}
}
inline int pr(int x){
int now=ch[x][0];
if(!now) return now;
while(ch[now][1]) now=ch[now][1];
splay(now);
return now;
}
inline void del(int x){
splay(x);
if(!ch[x][0]&&!ch[x][1]){ch[fa[x]][0]=0;fa[x]=0;return ;}
if(!ch[x][0]){ch[fa[x]][0]=ch[x][1];fa[ch[x][1]]=fa[x];ch[x][1]=fa[x]=0;return;}
if(!ch[x][1]){ch[fa[x]][0]=ch[x][0];fa[ch[x][0]]=fa[x];ch[x][0]=fa[x]=0;return;}
int now=x,f=fa[x],tmp=pr(x);
//cout<<now<<" "<<f<<" "<<tmp;
fa[ch[now][1]]=tmp,ch[tmp][1]=ch[now][1];
ch[f][0]=tmp,fa[now]=ch[now][0]=ch[now][1]=0;
}
inline void insert(int id,int x){
if(!ch[id][0]){ch[id][0]=x;fa[x]=id;return ;}
int now=ch[id][0],f=id;
while(true){
f=now,now=ch[now][now<x];
if(!now){
fa[x]=f,ch[f][f<x]=x;
splay(x);break;
}
}
}
inline void work(){
cin>>n>>q;
for(int i=1;i<=n;i++) fa[i]=i+n,ch[i+n][0]=i;
while(q--){
int op,x,y;cin>>op;
if(op==1) cin>>x>>y,del(x),insert(y+n,x);
if(op==2)cin>>x>>y,fa[ch[x+n][0]]=y+n,fa[ch[y+n][0]]=x+n,swap(ch[y+n][0],ch[x+n][0]);
if(op==3)cin>>x,cout<<fa[getrt(x)]-n<<"\n";
}
}
}
signed main(){
ios::sync_with_stdio(false);
//cin.tie(0),cout.tie(0);
return Opshacom::work(),0;
}
```