#5733. 「OOI 2026 Day1」参赛者入场

标签: 传统 | 时间限制: 3000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2026 Day1 T1 「Выход участников」 / 「Participants entry」。

在某次程序设计公开赛中，共有 $n$ 名选手参加，编号从 $1$ 到 $n$。编号为 $i$ 的选手穿着颜色为 $a_i$ 的衣服。比赛组织者准备依次邀请选手进入赛场。为了让入场过程看起来更具观赏性，他们希望避免连续入场的两名选手穿着颜色相同的衣服。为此，选手们将按照以下算法依次入场：

• 第一名进入赛场的选手是编号为 $1$ 的选手。
• 随后，每次邀请入场的选手，其衣服颜色必须与前一名进入的选手不同。若有多个符合条件的选手，则选择其中编号最小的那位。
• 最后，如果剩余所有选手的衣服颜色都与最后进入的那名选手相同，则剩下的所有选手按编号升序入场。

在比赛前一晚，组织者已经准备好了选手入场方案，但就在开赛前，他们发现编号相邻的选手有时会交换衣服。这显然会导致原有的方案不再符合规则，组织者需要制定一套新的方案。

你需要回答以下两种类型的询问：

1. 编号为 $x_i$ 和 $(x_i + 1)$ 的两名选手交换衣服。
2. 假设选手们根据上述算法开始入场，在考虑了之前所有交换操作的情况下，求出编号为 $y_i$ 的选手是第几个进入赛场的。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(1 \leq n \leq 500000, 1 \leq q \leq 500000)$，分别表示参赛选手的数量和询问的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \leq a_i \leq n)$，表示按编号排序的选手衣服的初始颜色。

接下来的 $q$ 行描述了询问。其中第 $i$ 行开头包含一个整数 $t_i$ $(1 \leq t_i \leq 2)$，表示第 $i$ 个询问的类型。

1. 如果 $t_i = 1$，则该行接下来包含一个整数 $x_i$ $(1 \leq x_i < n)$。在这种情况下，第 $i$ 个询问表示编号为 $x_i$ 和 $(x_i + 1)$ 的选手交换衣服。
2. 如果 $t_i = 2$，则该行接下来包含一个整数 $y_i$ $(1 \leq y_i \leq n)$。在这种情况下，第 $i$ 个询问需要求出，在考虑之前所有衣服交换的情况下，按照上述算法，编号为 $y_i$ 的选手是第几个入场的。

输出格式

对于每个第二类询问，在单独的一行中输出一个整数，即该询问的答案。

题目保证至少存在一个第二类询问。

样例 1

输入

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

输出

2
4
3
10
2
3
4
6
10

在第一个样例中，初始状态下选手入场的顺序为：

$$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$ 的选手交换衣服后，选手的衣服颜色如下：

$$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$ 的选手交换衣服后，选手的衣服颜色如下：

$$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$ 的选手第四个出场。

样例 2

输入

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

输出

1
2
2
2
5
4

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	附加限制	子任务依赖
$1$	$7$	$n, q \leq 500$	$0$
$2$	$9$	$n, q \leq 5000$	$0, 1$
$3$	$5$	$n, q \leq 10000$	$0, 1, 2$
$4$	$10$	$n, q \leq 100000$	$0, 1, 2, 3$
$5$	$8$	$n, q \leq 200000$	$0, 1, 2, 3, 4$
$6$	$7$	$n, q \leq 300000$	$0, 1, 2, 3, 4, 5$
$7$	$9$	$1 \leq a_i \leq 2$	-
$8$	$9$	$1 \leq a_i \leq 5$	$7$
$9$	$11$	对于任何 $i \neq j$，有 $a_i = 1$ 或 $a_i \neq a_j$；若 $t_i = 2$，则 $y_i = \lceil \frac{9n}{10} \rceil$	-
$10$	$8$	对于任何 $i \neq j$，有 $a_i = 1$ 或 $a_i \neq a_j$	$9$
$11$	$9$	若 $t_i = 2$，则 $y_i = \lceil \frac{9n}{10} \rceil$	$9$
$12$	$8$	无附加限制	$0$ - $11$