P16363 [OOI 2026] Participants entry
题目描述
在一次面向中小学生的公开编程奥林匹克竞赛中，共有 $n$ 名参赛者，编号为 $1$ 到 $n$。第 $i$ 名参赛者穿着一件颜色为 $a_i$ 的 T 恤。比赛组织者计划依次邀请参赛者进入竞赛大厅。为了使这一过程在视觉上赏心悦目，他们希望避免出现连续两名穿着相同颜色 T 恤的参赛者入场的情况。为此，参赛者将按照以下算法被邀请：
- 第一个进入竞赛大厅的是第 $1$ 号参赛者。
- 每次邀请的参赛者，其 T 恤颜色必须与最后入场的那名参赛者的颜色不同。如果有多名这样的参赛者，则选择其中编号最小的。
- 最后，如果所有剩余参赛者的 T 恤颜色都与最后入场的那名参赛者相同，则剩余的所有参赛者按照其编号递增的顺序被邀请入场。
在竞赛前夕，组织者拟定了一份参赛者入场计划，但在开幕式即将开始前，他们注意到相邻编号的参赛者有时会交换 T 恤。自然，这导致原来的计划不再符合规则，组织者需要制定一份新的计划。
你需要处理两种类型的询问：
- 编号为 $x_i$ 和 $(x_i + 1)$ 的两名参赛者交换 T 恤。
- 找出在所有先前的 T 恤交换均已发生的前提下，如果参赛者从第 $1$ 号开始按照上述算法依次入场，那么编号为 $y_i$ 的参赛者将以第几个顺序入场。
输入格式
第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 500\,000$, $1 \le q \le 500\,000$) —— 参赛者人数与询问次数。
第二行包含 $n$ 个整数 $a_1$, $a_2$, $\ldots$, $a_n$ ($1 \le a_i \le n$) —— 参赛者 T 恤初始颜色，按编号顺序给出。
接下来的 $q$ 行描述询问。第 $i$ 行中有一个整数 $t_i$ ($1 \le t_i \le 2$) —— 第 $i$ 个询问的类型。
- 若 $t_i = 1$，则接下来一行包含一个整数 $x_i$ ($1 \le x_i < n$)。此时，第 $i$ 个询问要求编号为 $x_i$ 和 $(x_i + 1)$ 的参赛者交换 T 恤。
- 若 $t_i = 2$，则接下来一行包含一个整数 $y_i$ ($1 \le y_i \le n$)。此时，在第 $i$ 个询问中，你需要输出在所有先前的 T 恤交换均已发生的前提下，参赛者从第 $1$ 号开始按照上述算法入场时，编号为 $y_i$ 的参赛者入场的顺序。
输出格式
对于每个第二类询问，你应当在一行中输出一个整数，作为该询问的答案。
数据保证至少有一个第二类询问。
说明/提示
### 样例解释
在第一个样例中，初始配置下，参赛者按如下顺序进入竞赛大厅：
$$1, \quad 2, \quad 4, \quad 3, \quad 5, \quad 6, \quad 8, \quad 7, \quad 9, \quad 10$$
也就是说，第 $2$ 号参赛者第二个入场，第 $3$ 号参赛者第四个入场，第 $4$ 号参赛者第三个入场，第 $10$ 号参赛者第十个入场。
在第 $1$ 号和第 $2$ 号参赛者交换 T 恤后，参赛者的 T 恤颜色依次为：
$$1, \quad 3, \quad 1, \quad 2, \quad 2, \quad 1, \quad 1, \quad 2, \quad 2, \quad 2$$
因此，在这次交换之后，参赛者将按如下顺序入场：
$$1, \quad 2, \quad 3, \quad 4, \quad 6, \quad 5, \quad 7, \quad 8, \quad 9, \quad 10$$
也就是说，第 $2$ 号参赛者第二个入场，第 $3$ 号参赛者第三个入场，第 $4$ 号参赛者第四个入场，第 $5$ 号参赛者第六个入场，第 $10$ 号参赛者第十个入场。
在第二个样例中，初始配置下，参赛者按如下顺序入场：
$$1, \quad 2, \quad 5, \quad 3, \quad 6, \quad 4, \quad 7, \quad 8, \quad 9, \quad 10$$
也就是说，第 $1$ 号参赛者第一个入场。
在第 $1$ 号和第 $2$ 号参赛者交换 T 恤后，颜色依次为：
$$2, \quad 1, \quad 2, \quad 2, \quad 3, \quad 4, \quad 5, \quad 6, \quad 7, \quad 8$$
因此，入场顺序变为：
$$1, \quad 2, \quad 3, \quad 5, \quad 4, \quad 6, \quad 7, \quad 8, \quad 9, \quad 10$$
即第 $2$ 号参赛者第二个入场。
在第 $2$ 号和第 $3$ 号交换后，颜色为：
$$2, \quad 2, \quad 1, \quad 2, \quad 3, \quad 4, \quad 5, \quad 6, \quad 7, \quad 8$$
入场顺序变为：
$$1, \quad 3, \quad 2, \quad 5, \quad 4, \quad 6, \quad 7, \quad 8, \quad 9, \quad 10$$
即第 $3$ 号参赛者第二个入场。
在第 $3$ 号和第 $4$ 号交换后，颜色为：
$$2, \quad 2, \quad 2, \quad 1, \quad 3, \quad 4, \quad 5, \quad 6, \quad 7, \quad 8$$
入场顺序变为：
$$1, \quad 4, \quad 2, \quad 5, \quad 3, \quad 6, \quad 7, \quad 8, \quad 9, \quad 10$$
即第 $4$ 号参赛者第二个入场。
在第 $4$ 号和第 $5$ 号交换后，颜色为：
$$2, \quad 2, \quad 2, \quad 3, \quad 1, \quad 4, \quad 5, \quad 6, \quad 7, \quad 8$$
入场顺序变为：
$$1, \quad 4, \quad 2, \quad 5, \quad 3, \quad 6, \quad 7, \quad 8, \quad 9, \quad 10$$
即第 $3$ 号参赛者第五个入场，第 $5$ 号参赛者第四个入场。
### 计分
本题的测试数据分为 12 组。每组仅在通过该组内全部测试以及此前某些组的全部测试后，才能获得分数。注意，某些组不要求通过样例测试。**离线测试**表示你提交的解答在该组上的测试结果将仅在比赛结束后公布。每组的最终得分等于你所有提交的解答中在该组测试上获得的最高分。
| 子任务编号 | 分数 | 额外限制 | 必过组别 | 备注 |
|:---:|:---:|:---:|:---:|:---:|
| | | $n, q$ | | |
| 0 | 0 | -- | -- | 题面样例。 |
| 1 | 7 | $n, q \le 500$ | 0 | |
| 2 | 9 | $n, q \le 5\,000$ | 0, 1 | |
| 3 | 5 | $n, q \le 10\,000$ | 0--2 | |
| 4 | 10 | $n, q \le 100\,000$ | 0--3 | |
| 5 | 8 | $n, q \le 200\,000$ | 0--4 | |
| 6 | 7 | $n, q \le 300\,000$ | 0--5 | |
| 7 | 9 | -- | -- | $1 \le a_i \le 2$ |
| 8 | 9 | -- | 7 | $1 \le a_i \le 5$ |
| 9 | 11 | -- | -- | 对任意 $i \neq j$：$a_i = 1$ 或 $a_i \neq a_j$
若 $t_i = 2$，则 $y_i = \left\lceil \frac{9n}{10}\right\rceil$ | | 10 | 8 | -- | 9 | 对任意 $i \neq j$：$a_i = 1$ 或 $a_i \neq a_j$ | | 11 | 9 | -- | 9 | 若 $t_i = 2$，则 $y_i = \left\lceil \frac{9n}{10}\right\rceil$ | | 12 | 8 | -- | 0--11 | **离线测试。** | 翻译由 DeepSeek V4 Pro 完成
若 $t_i = 2$，则 $y_i = \left\lceil \frac{9n}{10}\right\rceil$ | | 10 | 8 | -- | 9 | 对任意 $i \neq j$：$a_i = 1$ 或 $a_i \neq a_j$ | | 11 | 9 | -- | 9 | 若 $t_i = 2$，则 $y_i = \left\lceil \frac{9n}{10}\right\rceil$ | | 12 | 8 | -- | 0--11 | **离线测试。** | 翻译由 DeepSeek V4 Pro 完成