Luogu P13272 [NOI 2025] 序列变换

rizynvu · 2025-07-15 14:38:48 · 题解

cnblogs。

首先因为这题要计数，所以尝试去找一个刻画方式刻画出所有能被 a 生成的序列。

考虑操作实际就是让 a_i, a_{i + 1} 同时减去 \min\{a_i, a_{i + 1}\}。

在这之后一定会有一个数变为 0，且发现若操作的两个数中有 0，那么情况一定不变。

于是可以知道，如果多次选择了 (i, i + 1)，那么除第一次的操作肯定都是无效的。
那么直接指定每对 (i, i + 1) 至多被操作一次即可。

考虑操作时若 a_i \le a_{i + 1}，那么认为有 i\to i + 1；若 a_i \ge a_{i + 1}，那么有 i\gets i + 1（相等会有点问题，但是这里先暂时不考虑）。
这个边集一定能被分成若干个 \cdots\to\to\to\gets\gets\gets\cdots 的连续段，即左端从 l，右端从 r 往内汇聚，直到一个分界线 k 挡住了两测。

于是可以首先预处理出单侧的情况，记 lv_{l, k} 表示 l 汇聚到 k 时的值，易知有 lv_{l, l} = a_l, lv_{l, k + 1} = a_{k + 1} - lv_{l, k}。
需要保证中途都是可以操作的，即若 lv_{l, k} < 0，那么其实都走不到 k 这里，从 k 开始的 lv_{l, k} 都是不合法的。
同理定义 rv_{r, k}。

那么考虑暴力的做法，直接枚举 (l, r, k)，首先肯定要满足 l, r 都能走到 k，然后再来分讨一下 k 处的情况：

（这里与 a_k 比较只是因为前面定义的 lv_{l, k}, rv_{r, k} 相加时会多一个 a_k，实际上还是与 0 比较。）

于是现在就有了个 \mathcal{O}(n^3) 的做法，不过会发现这个做法其实有点问题，计数的时候可能会计重。

例如 a = [1, 1, 1, 1]，会认为 [1, 2], [3, 4], [1, 4] 都可以消除，那这就爆了。
思考一下原因，对于 (l, r, k)，其实如果删除一段前缀或后继（不包括 k），假设通过这段后得到的值是 x，那么对最终 a_k 的影响肯定是有 +x 或 -x 的，那么肯定就需要另一边同样调整以使最终 a_k 不变，但是这样又会影响周边的段继续修改，所以一定会继续往外扩张的，一定不合法——吗？
于是发现了问题：当 x = 0 时，且如果换一个方向传入的值也是 0 时，那么这一段是可以分到任意一边的。

为了解决这个问题，只需要考虑小修一下 lv_{l, k}, rv_{r, k} 的定义：当 \le 0 时就是不合法的。这样的 \mathcal{O}(n^3) 做法就是正确的。