题解：AT_abc395_d [ABC395D] Pigeon Swap

da_ke · 2025-03-02 09:10:09 · 题解

fyy 是一个珂愛的女孩子，有一天她购得 N 只珂愛的 da_ke。

她初始将编号 i 的 da_ke 放置在 i 号笼子里。

随后，她进行 Q 次操作，操作分为 2 类

1. 将 a 号 da_ke 放入 b 号笼子
2. 将 a 号笼子和 b 号笼子里的所有 da_ke 互换。

fyy 可以在任意时刻问妳某个 da_ke 在哪个笼子里。

fyy 非常喜欢 da_ke，于是她买了很多只，于是妳要使用一种非常高效的算法来回答她的问题。

「珂愛的我」（下简记为我）想到，对于操作 1 是容易的，经常刷题的朋友都知道，对于操作 2 不容易单个处理，必须整体处理。

对于操作 2，我想到将笼子 a 和笼子 b 整体交换。但这将导致 a 和 b 的位置改变，da_ke 的位置也将改变，如何处理呢？

问题过于抽象，为了更加形象（笔者赛时也是这么想的），我将问题形象化。

将笼子和 da_ke 一起放在数轴上。为了语言描述，我常用「da_ke 本身」和「笼子本身」这两个短语。

• 对于所有操作 1，我们只需挪动 da_ke 本身的位置即可。
• 对于所有操作 2：
  • 保证 da_ke 本身的位置不变（解题的关键）。
  • 只交换笼子本身达到效果。
  • 更新笼子本身的位置。

以上是一些感性认识，我们现在将其转换为形式化语言。

记笼子 i 的坐标位置为 S_i，坐标位置 i 的笼子为 E_i，编号为 i 的 da_ke 目前被关在坐标位置为 H_i 的笼子里。

• 对于操作 1，H_a \leftarrow S_b。
• 对于操作 2：
  • 将 a,b 的坐标位置互换，达到 S_a'=S_b,S_b'=S_a 的效果。

代码是简单的。

int main()
{
    int N,Q;
    cin>>N>>Q;
    vector<int> st(N+1),ed(N+1),home(N+1); // st 为某个巢的坐标位置，ed 为某个坐标位置的巢。 
    rep(i,1,N) st[i]=i,ed[i]=i,home[i]=i;
    rep(i,1,Q)
    {
        int o;
        cin>>o;
        // 操作时应保证，鸽子是不动的。
        if(o==1)
        {
            int a,b;
            cin>>a>>b;
            home[a]=st[b];
        }
        /*
        .....a.....b....
        .....b.....a....
        */
        if(o==2)
        {
            int a,b;
            cin>>a>>b;
            ed[st[a]]=b,ed[st[b]]=a;
            swap(st[a],st[b]);
        }
        if(o==3)
        {
            int a;
            cin>>a;
            cout<<ed[home[a]]<<endl;
        }
    }
}

// 路虽远行则将至，事虽难做则必成。

AC 记录