题解：CF2252D Array Replacement

hqc20230131 · 2026-08-07 11:58:19 · 题解

题目给出了这样的操作：对于奇偶性相同的 a_{i-1} 和 a_{i+1}，把原来的三元组 (a_{i-1},a_{i},a_{i+1}) 变成 (a_{i-1},a_{i+1}+a_{i-1}-a_{i},a_{i+1})。

设差分数组 d_{i}=a_{i+1}-a_{i}，那么对 i 进行操作了以后，会发生以下的变化：

可以发现，对 i 进行操作，实际上就是交换 (d_{i-1},d_{i})。那么接着考虑奇偶性。

如果 a_{i-1} 和 a_{i+1} 是相同的奇偶性，那么 a_{i+1}-a_{i-1} 必定是偶数，所以有

所以当 d_{i}+d_{i-1} 是偶数时，满足进行交换的条件，所以当 d_{i} 和 d_{i-1} 的奇偶性相同时，同样满足进行交换的条件。

那么把 d 数组分成若干区间，每一个区间内的 d_{i} 奇偶性相同，对每一个区间从小到大排序，对 d 进行前缀和。最后输出。

时间复杂度为 \Theta \left(n\log_{2}{n}\right)。

通过记录以及代码。