题解 CF2252D Array Replacement

· · 题解

题解 CF2252D Array Replacement

同场其他题

题意

给定长为 n 的序列 a，每次操作可以选择满足 1<i<n 且 a_{i-1}\equiv a_{i+1}\pmod 2 的 a_i，并将 a_i 改为 a_{i-1}+a_{i+1}-a_i。求操作若干次后所能得到的字典序最小的序列。

数据范围：多测，\sum n\le 2\times 10^5。

做法

:::error[死亡回放]{open}

这种让你操作的题可以先试着找操作到底在干什么。其实就是交换差分数组的两项：

  • 设原数组中一个长度为 3 的子段 a_1,a_2,a_3 的差分数组是 d_1=a_2-a_1,d_2=a_3-a_2。
  • 对 a_2 进行操作所得 a_2'=a_3+a_1-a_2。
  • 于是新的差分数组 d_1'=(a_3+a_1-a_2)-a_1=a_3-a_2=d_2,d_2'=a_3-(a_3+a_1-a_2)=a_2-a_1=d_1，即将 d_1 与 d_2 进行了交换。

内容来自文中《P7962 [NOIP2021] 方差》的题解。

然后本题我**的又没做出来。 :::

以上是本题的提示部分。

由于 a_{i-1} 和 a_{i+1} 的奇偶性须相同，所以只有同奇偶的连续段内可以操作，且 a_{i-1}+a_{i+1} 始终为偶，即 a_i 操作前后奇偶性不变。所以对于每个奇偶的连续段内部，将差分数组分别排序，然后复原即可。

单组复杂度 O(n\log n)。