P8505 题解
lzqy_
·
·
题解
爆踩一下去年的自己。
首先还是考虑 f 的转移，即：
\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 的情况。
代码没什么不同的，只是给出一种更正常的思维方式。