Visits: 250

ARC102F Revenge of BBuBBBlesort!

题意

• 给定一个 $1 \sim n$ 的排列 $p$。
• 每次操作可以选择一个满足 $p_{i-1} > p_i > p_{i+1}$ 的 $i$，将 $p_{i-1}$ 和 $p_{i+1}$ 交换。
• 问能否将 $p$ 变成 $1,2,3,\cdots,p$。
• $n \le 3 \times 10^5$。

题解

一个显然的结论是：相邻两个下标中，至多一个下标进行过操作。

于是我们可以把所有操作过的 $i$ 分为若干个极长段，每个极长段为一个公差为 $2$ 的等差数列；不同极长段之间至少间隔两个数，且相互之间独立。

对于一个长度为 $k$ 极长段，不妨设下标为 $2,4,6,\cdots,2k$，其影响到的下标范围为 $[1, 2k+1]$，称之为一个连续段。

考虑 $p$ 和目标的升序排列中不变的位置，显然不变的位置只能是操作过的 $i$，以及不同连续段之间间隔的位置。因此根据不变的位置我们可以贪心地划分出连续段，如果出现矛盾则说明无解。

现在考虑一个连续段内如何判断是否可行。

判断了值域是否在连续段的范围内后，剩下的就是下标为 $1,3,5,\cdots,2k+1$ 的位置能否经过题目要求的操作还原。

反过来考虑，考虑 $1,2,3,\cdots,2k+1$ 只在偶数位上操作的情况下会生成怎样的排列。

注意到，每个奇数位上的数一定只会往一个方向运动，因此向同一个方向运动的数的相对位置不变。

这个条件是必要的，同样也是充分的。即我们可以将 $1,3,5,\cdots,2k+1$ 划分为两个集合，一个集合在相对位置不变的情况下全部向左移动，另一个集合在相对位置不变的情况下全部向右移动，所能得到的任何一种情况都是合法的。

证明大概就是，向左移动的数在不超过前面的数的情况下一定可以不断向左，向右移动的数在不超过前面的数的情况下一定可以不断向右。

总结一下，如果这个排列合法，则可以：

1. 贪心地根据不变的位置将排列划分成若干个连续段。
2. 每个段的值域恰好等于下标。
3. 段内向同一个方向移动的元素相对位置不变。

显然可以 $\mathcal O(n)$ 判定。

代码

#define Fail prints("No"), exit(0);
const int N = 3e5 + 7;
int n, p[N];

inline bool pd(int l, int r) {
    if (l == r) return 0;
    int L = 0, R = 0;
    for (int i = l; i <= r; i += 2)
        if (p[i] < l || p[i] > r) return 0;
        else if (i < p[i]) {
            if (L && p[i] < L) return 0;
            else L = p[i];
        } else {
            if (R && p[i] < R) return 0;
            else R = p[i];
        }
    return 1;
}

int main() {
    rd(n), rda(p, n);
    for (int l = 1, r = 1; l <= n; l = ++r) {
        if (p[r] == r) continue;
        while (r + 2 <= n && p[r+1] == r + 1 && p[r+2] != r + 2) r += 2;
        if (!pd(l, r)) Fail;
    }
    prints("Yes");
    return 0;
}