题解：AT_abc395_d [ABC395D] Pigeon Swap

赛时糊的抽象做法。

题面

有

N

只标有

1, 2, \ldots, N

的鸽子和

N

个标有

1, 2, \ldots, N

的鸽巢。
最初，鸽子

i

在

(1 \leq i \leq N)

巢中。

(1 \leq i \leq N)

在巢

i

中。

Q

次操作，有三种：

给定整数 $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;
}

题解：AT_abc395_d [ABC395D] Pigeon Swap

文章操作

题面

解法

代码

相关推荐

评论

题解：AT_abc395_d [ABC395D] Pigeon Swap