这是官方题解的 AI 翻译，使用了 GPT-5.5 Thinking 模型。

题意相关观察

先直接模拟整个过程。按编号从小到大依次扫描每个选手：

• 如果当前选手的颜色和上一个被放出来的选手颜色相同，就把他放进队列；
• 否则，就把当前选手记成下一个要被放出来的人，然后如果队列非空，就先把队首的人放出来；
• 所有选手处理完以后，再把队列里剩下的人依次放出来。

这样就能线性地模拟一次过程，因此朴素做法的复杂度是 $O(qn)$。

接下来考虑一个关键性质：如果在模拟过程中，队列为空，且当前选手的颜色和上一个被放出来的选手颜色不同，那么这个选手最终一定会站在自己的编号位置上。并且，比他编号更小的那些人，已经不会再影响他以及后面所有人的排列了。也就是说，从这个人开始，可以把过程看成一次“重新开始”。

建图刻画“重新开始”的位置

假设现在从编号 $i$ 的选手开始重新考虑。怎么找到下一个也可以视作“重新开始”的位置呢？

把所有颜色等于 $a_i$ 的位置记为 $+1$，其余位置记为 $-1$。设最小的下标 $j$ 满足区间和

那么这个 $j$ 就是我们要找的位置。于是，对每个位置 $i$，连一条有向边到 $p_i = j$。这样所有边会构成一片有向森林。

如何回答询问

对于一次询问，我们从第一个选手开始，沿着森林中的边不断往后跳，只要下一次“重新开始”的位置编号还不超过 $y$，就继续跳。

假设最后停在了 $i$。根据前面的性质，此时可以认为整个过程是从 $i$ 开始重新进行的。

再观察区间 $[i, p_i - 1]$ 上的排列：

• 位置 $i, i + 2, i + 4, \dots, p_i - 1$ 上，站的都是颜色为 $a_i$ 的选手；
• 位置 $i + 1, i + 3, i + 5, \dots, p_i - 2$ 上，站的是其它颜色的选手。

因此，要确定选手 $y$ 的最终位置，只需要知道在他前面有多少个颜色为 $a_i$ 的人即可。这个值可以在颜色 $a_i$ 的出现位置数组上二分得到，而这个数组也可以在修改操作下动态维护。

于是，原问题被拆成了两个部分：

1. 当相邻两个人的颜色发生变化时，如何动态维护这片森林；
2. 如何快速找到覆盖位置 $y$ 的那条边。

在满分做法里，这两部分可以用 link-cut tree 完成。当然，用根号分治仔细实现，也同样可以拿到满分。

如何快速找到覆盖位置 $y$ 的边

第二部分实际上可以用 link-cut tree 的 expose 操作解决。

从点 $1$ 做一次 expose，就能把所有“可以视作重新开始”的位置组成的一条链抽出来。接下来在得到的 splay 上往下走，就能找到对应的那个位置，也就找到了覆盖 $y$ 的那条边。

相邻交换时，边会如何变化

现在只剩下第一部分：当相邻的两个位置 $x, x + 1$ 的颜色交换后，哪些 $p_i$ 会改变？

先看不会受影响的部分：

• 对于颜色既不是 $a_x$ 也不是 $a_{x+1}$ 的那些位置，原来这两个点对前缀和的贡献都是 $-1$，交换以后仍然如此，所以没有影响；
• 如果 $a_x = a_{x+1}$，那就更是什么都不会变。

因此，只需要讨论 $a_x \ne a_{x+1}$ 的情况。

首先，$x$ 和 $x + 1$ 自己的出边一定会变。除此之外，还可能各自再影响至多一条别人的出边。

以颜色 $a_x$ 为例：位置 $x, x + 1$ 对应的贡献从 $+1, -1$ 变成了 $-1, +1$。于是，对于某个颜色为 $a_x$ 的起点 $i$，原来从 $i$ 往后做前缀和时，可能在位置 $x$ 之前还没有归零，但交换后恰好会在 $x$ 处变成 $0$。这说明交换之前，前缀和到 $x$ 为止正好多了 $2$。

所以，我们只需要找到这样一个位置：它对应的前缀和值比位置 $x$ 处小 $2$，那么原本指向后面的那条边，现在就应该改为指向 $x$。并且，由边的构造方式可知，这样的边至多只有一条。

这个过程可以借助颜色 $a_x$ 对应的一棵线段树来完成。在线段树里，按该颜色出现的顺序维护“到这一项为止的前缀和”。注意这里只需要在这种出现位置上维护即可，因为在两个同色位置之间，前缀和的变化是线性的。

同理，对于颜色 $a_{x+1}$ 也能得到至多一个候选位置，它的 $p_i$ 也可能发生变化。

至于新边的终点该指向哪里，则只需要在线段树上再做一次查询：找到位置 $i$ 之后，第一个使得前缀和比 $i$ 之前小 $1$ 的位置即可。

复杂度

这样就得到了一个时间复杂度为 $O(q \log n)$ 的做法。

另外，题目还可以做到下面这些复杂度：

• 用 treap 代替 link-cut tree 里的 splay，可以做到 $O(q \log^2 n)$；
• 用分块做整套维护，可以做到 $O(q \sqrt n)$。具体做法是把整个序列按块划分，并为每个元素维护一个压缩跳跃指针，指向沿着边不断向上走后，第一个离开当前块的位置。一次修改只会影响至多 $4$ 个块，而查询时不断沿着这些压缩跳跃走，直到到达包含询问位置的块即可。