比较套路的一个题。
首先你先想 DP 怎么做。
设 \(f_{i, 0/1}\) 表示到了 \(i\) 目前正在上升还是正在下降最长长度是多少，不难发现这个只和相邻两个数的大小关系有关。
发现区间加并不影响区间内相邻大小关系，只影响交界处的关系，所以这是一个单点改。
我们用一个矩阵维护 DP 数组，然后发现就变成了单点改矩阵，区间广义矩阵乘法，显然是好做的。
常数可能会有点大。
比较套路的一个题。
首先你先想 DP 怎么做。
设 \(f_{i, 0/1}\) 表示到了 \(i\) 目前正在上升还是正在下降最长长度是多少，不难发现这个只和相邻两个数的大小关系有关。
发现区间加并不影响区间内相邻大小关系，只影响交界处的关系，所以这是一个单点改。
我们用一个矩阵维护 DP 数组，然后发现就变成了单点改矩阵，区间广义矩阵乘法，显然是好做的。
常数可能会有点大。