自动搬运

查看原文

来自洛谷，原作者为

	lzqy_ 生而绚烂，璀璨如花。

搬运于2025-08-24 22:39:40，当前版本为作者最后更新于2022-10-22 19:32:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

爆踩一下去年的自己。

首先还是考虑 $f$ 的转移，即：

$$ f_i=\left\{ \begin{aligned} f_{i+1}+1\;(a_i\leq a_{i+1}) \\ f_{i+3}+2\;(a_i>a_{i+1}) \end{aligned} \right. $$

也就是说，$f_i$ 的值是 $(f_{i+1}+1)$ 和 $(f_{i+3}+2)$ 中的任意一个（因为 $a$ 可以随便取），而取值个数和 $f_{i+1}+1=f_{i+3}+2$ 是否成立有关，也就是只和 $f_{i+1},f_{i+3}$ 的差有关。

所以考虑转移时维护 $f_{i+1}-f_{i+2},f_{i+2}-f_{i+3}$ 两个值，由 $f_{n+1}=0,f_{n}=1,f_{n-1}=2$ 出发，可以发现，这两个差值的组合一共只有三种，即 $\{1,1\},\{0,1\},\{1,0\}$，所以维护一个 $3\times 3$ 的转移矩阵即可。修改操作用线段树维护。

至于判断二元组是否合法，只需要修改后判断是否有解即可，若无解再撤销。注意本身有解而取模后答案为 $0$ 的情况。

代码没什么不同的，只是给出一种更正常的思维方式。