题解：CF2138B Antiamuny Wants to Learn Swap

Engulf · 2025-09-09 09:00:19 · 题解

结论：f([l, r]) \neq g([l, r]) 的充要条件是：区间 [l, r] 存在 l \le i < j < k \le r \ \wedge \ a_i > a_j > a_k。

充分性：若区间 [l, r] 存在 l \le i < j < k \le r \ \wedge \ a_i > a_j > a_k，当交换相邻两项使得 j = i + 1, k = j + 1 的时候，因为要最小化 f，肯定会执行一次操作 2，直接交换 a_i 和 a_k，跳过 a_j，省下 1 次操作，所以 f([l, r]) \neq g([l, r])。

必要性：冒泡排序一个区间的操作数是恒定的，但 f([l, r]) \neq g([l, r])，说明 一定执行了操作 2。而操作 2 只有在 [a_{j - 1}, a_j, a_{j + 1}] \ \wedge \ a_{j - 1} > a_j > a_{j + 1} 的时候操作，才能比操作 1 省下 1 次，使得 f([l, r]) \neq g([l, r])，而又因为最多执行 1 次操作 2，所以 a_{j - 1} 和 a_{j + 1} 可以分别往前往后移动。于是区间 [l, r] 就会存在 l \le i < j < k \le r \ \wedge \ a_i > a_j > a_k。

充要条件可以归约问题。

问题转化为，q 次询问区间 [l, r] 是否存在 l \le i < j < k \le r \ \wedge \ a_i > a_j > a_k。

我们肯定希望 i, k 离 j 越近越好，这样可以覆盖到更多的询问。所以我们要求出：

这是经典问题，可以单调栈 \Theta(n) 求出。

现在，每个 j 可以对 l \le i < k \le r 的询问 [l, r] 贡献，就是对于每个询问，寻找是否存在 l \le i < k \le r，这是二维偏序问题，可以离线 + 树状数组解决。