题目详情题解（0）讨论（0）提交记录（0）

AT_abc395_d.[ABC395D] Pigeon Swap

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 NN 只鸽子（编号 1,2,…,N1,2,\ldots,N）和 NN 个巢（编号 1,2,…,N1,2,\ldots,N）。初始时，鸽子 ii（1≤i≤N1 \leq i \leq N）位于巢 ii 中。

接下来对鸽子进行 QQ 次操作，操作分为以下三种类型：

  • 类型 1：给定整数 a,ba,b（1≤a≤N1 \leq a \leq N，1≤b≤N1 \leq b \leq N）。将鸽子 aa 从当前所在的巢中取出，放入巢 bb。
  • 类型 2：给定整数 a,ba,b（1≤a<b≤N1 \leq a < b \leq N）。将巢 aa 中所有鸽子移动到巢 bb，同时将巢 bb 中所有鸽子移动到巢 aa。这两个移动操作是同时进行的。
  • 类型 3：给定整数 aa（1≤a≤N1 \leq a \leq N）。报告鸽子 aa 当前所在的巢的编号。

请输出所有类型 3 的操作的结果。

输入格式

输入通过标准输入给出，格式如下：

NN QQ
op1op_1
op2op_2
⋮\vdots
opQop_Q

其中，第 i+1i+1 行的 opiop_i 表示第 ii 次操作，格式为以下之一：

  • 若为类型 1 操作：
    1 a b
    表示以 aa 和 bb 为参数执行类型 1 操作。

  • 若为类型 2 操作：
    2 a b
    表示以 aa 和 bb 为参数执行类型 2 操作。

  • 若为类型 3 操作：
    3 a
    表示以 aa 为参数执行类型 3 操作。

输出格式

设类型 3 的操作共有 qq 个，输出 qq 行，每行对应一个类型 3 操作的查询结果（即鸽子所在巢的编号）。

输入输出样例

  • 输入#1

    6 8
1 2 4
1 3 6
3 2
2 4 5
3 2
1 4 2
3 4
3 2

    输出#1

    4
5
2
5

  • 输入#2

    1 2
1 1 1
3 1

    输出#2

    1

  • 输入#3

    30 15
3 3
2 8 30
2 12 15
2 2 17
1 19 1
2 7 30
3 12
3 8
2 25 26
1 13 10
1 16 10
2 16 29
2 1 21
2 6 11
1 21 8

    输出#3

    3
15
7

说明/提示

约束条件

  • 1≤N≤1061 \leq N \leq 10^6
  • 1≤Q≤3×1051 \leq Q \leq 3 \times 10^5
  • 所有操作均符合题目描述中的参数范围。
  • 输入中至少包含一个类型 3 操作。
  • 输入均为整数。

样例解释 1

操作过程中鸽子的移动如图所示（图片链接略）。类型 3 操作应报告的巢编号依次为 4,5,2,54,5,2,5，因此输出四行：4、5、2、5。

样例解释 2

在类型 1 操作中，可能存在将鸽子取出后又放回原巢的情况。

翻译由 DeepSeek R1 完成

输入解题思路，AI测评打分。不知道怎么写?

首页