AT_abc395_d

CloverArmeriaThrift · 2025-03-01 22:38:26 · 题解

前言

https://blog.csdn.net/ArmeriaLeap/article/details/145954559

在谎言中迷茫，试图躲避瓶颈。 可惜细节太多，浪费五发罚时。 一个绿名用户，被出题人卡住。 八十六分钟多，才看见一抹绿。

本题解 \LaTeX 格式可能不太美观，以内容为主。

题目大意

有一群鸽子和它们的窝，三种操作，你要在第三种的时候输出一个数。题面很简单，没有太多的文字游戏，自行阅读吧。这篇题解不提供题目翻译。

思路

想一想暴力，为什么会超时？正解需要对哪里进行优化？

观察第二种操作，发现它太吃操作了，是这道题的时间复杂度瓶颈。本文将介绍一种时间复杂度为 O(Q) 的做法。对于第二种操作，显然不能暴力模拟——为了不超时，我们绝对不能交换鸽子！作为口是心非的 OIer，让我们充分发扬人类智慧：做个记号，下面算答案的时候注意一下即可。

具体地，我们要维护三个数组：

有点绕，好好理解一下。毕竟我调了近一个小时，这肯定不是什么简单的东西。

现在来说一下三种操作的实现。

• 第一种操作——单只鸽子 x 搬到 y ：a[x]=c[y];
• 第二种操作——x 和 y 两个窝集体交换：swap(b[c[x]],b[c[y]]); swap(c[x],c[y]);
• 第三种操作——输出 x 在哪里：cout << b[a[x]] << endl;

  代码实现

  Submission #63299010

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int n, q;
int a[1000010];
int b[1000010];
int c[1000010];

int main()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        a[i] = b[i] = c[i] = i;
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int x, y;
            cin >> x >> y;
            a[x] = c[y];
        }
        else if (op == 2)
        {
            int x, y;
            cin >> x >> y; 
            int cx = c[x];
            int cy = c[y];
            b[cx] = y; c[y] = cx;
            b[cy] = x; c[x] = cy;
        }
        else
        {
            int x; cin >> x;
            cout << b[a[x]] << endl;
        }
    }
    return 0;
}