题解：P13272 [NOI 2025] 序列变换
D2T1
·
·
题解
一个 O(n^2) 的，考场数据所有点用时小于 0.6s 的做法。
先考虑第一问。显然的发现是：
- 对于 (i,i+1) 或 (i,i-1)，只会操作一次。
- 不会先操作 (i,i+1) 再操作 (i-1,i)，因为先操作后 a_i 变为了 0，那么第二个操作要么不能进行，要么毫无意义。
- 不会先操作 (i,i-1) 再操作 (i+1,i)。
那么所有操作可以划分成若干不交的段，每一段 [l,r] 表示操作 (l,l+1),(l+1,l+2),...,(p-1,p) 以及 (r,r-1),(r-1,r-2),...,(p+1,p)，最后只剩一个 a_p\neq 0 或者 a_l\sim a_r 均为 0。
预处理 L_i,R_i 表示操作 (i,i-1),(i-1,i-2),... 一直能够操作到最左侧的 (L_i+1, L_i)，R_i 同理。那么一个区间 [l,r] 可以变为一个合法的段当且仅当 R_l\geq L_r。
假设最后区间 [l,r] 缩到了一个点 p\in[\max(l,L_r),\min(r,R_l)]，a_p 的值其实是非常好算的：[l,r] 内与 p 同奇偶的 a 和减去与 p 不同奇偶的 a 和。这个值与 p 的具体位置没有关系，只和 p 的奇偶性有关！具体地，对于合法段有：
- 若 \sum_{i=l}^r(-1)^ia_i=0，则这一段内的 a 可以全变为 0；
- 若 \sum_{i=l}^r(-1)^ia_i>0，则 [\max(l,L_r),\min(r,R_l)] 内所有偶数下标可以作为最终的 p；
- 若 \sum_{i=l}^r(-1)^ia_i<0，则 [\max(l,L_r),\min(r,R_l)] 内所有奇数下标可以作为最终的 p。
于是得到了第一问做法：设 f_i 表示前 i 个元素的最优解，枚举区间 [l,r] 判断是否合法，然后找到对应的类型，更新 f_r 即可。
最后是去重的问题。发现重的地方在哪呢？在于一个合法段可能拆分成一个 0 段和一个合法段，对应的唯一有值的 a 仍然相同。
需要改的地方非常简单：求解 L,R 时，若 i\to L_i 一路操作过去会使得 a_{L_i}=0，那么直接视作求得 L_i，break。R 同理。这样的话，一个合法段就不再能继续拆分。
总复杂度 O(n^2)，不需要任何数据结构。