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

AT_abc470_d.Inverse and Swap

普及/提高-

通过率：0%

时间限制：2.00s

内存限制：1024MB

AC君温馨提醒

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

题目描述

给定一个 11 到 NN 的排列

P=(P1,P2,…,PN).P=(P_1,P_2,\ldots,P_N).

接下来依次处理 QQ 次操作。

操作共有以下两种：

  • 1 x y：交换 PxP_x 和 PyP_y 的值。
  • 2：构造一个 11 到 NN 的排列

P′=(P1′,P2′,…,PN′),P'=(P'_1,P'_2,\ldots,P'_N),

满足对于所有 1≤i≤N1\le i\le N：

PPi′=i.P'_{P_i}=i.

然后使用 P′P' 替换当前的 PP。

可以证明，满足上述条件的排列 P′P' 唯一存在。

处理完全部操作之后，输出 P1,P2,…,PNP_1,P_2,\ldots,P_N。

输入格式

输入格式如下：

N Q
P1 P2 ⋯ PN
query1
⋮
queryQ

其中，第 qq 次操作 queryq 为以下两种格式之一：

1 x y

或者

2

输出格式

在一行中输出最终的

P1,P2,…,PN,P_1,P_2,\ldots,P_N,

相邻两个数之间用空格分隔。

输入输出样例

  • 输入#1

    5 5
2 1 3 5 4
1 2 4
2
1 2 3
1 3 4
2

    输出#1

    4 5 2 1 3

  • 输入#2

    7 4
3 7 5 6 4 2 1
2
2
2
2

    输出#2

    3 7 5 6 4 2 1

  • 输入#3

    10 8
7 3 2 4 8 5 10 9 1 6
2
1 4 10
1 6 9
2
1 9 10
1 3 10
2
1 4 6

    输出#3

    3 10 2 8 6 7 1 5 9 4

说明/提示

样例一解释

每次操作执行结束后，PP 分别为：

  • 第一次操作后：P=(2,5,3,1,4)P=(2,5,3,1,4)。
  • 第二次操作后：P=(4,1,3,5,2)P=(4,1,3,5,2)。
  • 第三次操作后：P=(4,3,1,5,2)P=(4,3,1,5,2)。
  • 第四次操作后：P=(4,3,5,1,2)P=(4,3,5,1,2)。
  • 第五次操作后：P=(4,5,2,1,3)P=(4,5,2,1,3)。

数据范围

  • 2≤N≤5×1052\le N\le5\times10^5
  • 1≤Q≤5×1051\le Q\le5\times10^5
  • (P1,P2,…,PN)(P_1,P_2,\ldots,P_N) 是 11 到 NN 的一个排列。
  • 对于类型 11 的操作，满足 1≤x<y≤N1\le x<y\le N。
  • 所有输入值均为整数。

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

首页