P13272

考虑答案形式，一次操作 $(i,i+1)$ 若 $a_i\ge a_{i+1}$ 则在 $i+1$ 上放一个 $\leftarrow$，若 $a_{i+1}\ge a_i$ 则在 $i$ 上放一个 $\rightarrow$。则操作情况形如若干个 $\rightarrow\rightarrow\rightarrow\leftarrow\leftarrow$。

考虑记 $v^{(\rightarrow)}_{i,j\ge i}$ 表示若从 $i$ 开始一直往右操作直至 $j$，最终 $a_j$ 的值，若过程中出现 $a_k>a_{k+1}(i\le k<j)$ 则 $v^{(\rightarrow)}_{i,j}$ 不合法。同理定义 $v^{(\leftarrow)}_{i,j\le i}$。对于一个极长的 $\rightarrow\leftarrow$ 区间 $[l,r]$ 考虑枚举最终非 $0$ 位置 $k$：（需有 $v^{(\rightarrow)}_{l,k},v^{(\leftarrow)}_{r,k}$ 合法）

将 $v^{(\rightarrow)}_{l,k}/v^{(\leftarrow)}_{r,k}$ 挪至不等号右边即退化为最终 $k$ 和 $k\pm 1$ 的比较，从而正确性显然。

如此记 $f_r$ 为仅考虑 $[1,r]$ 区间下 $\max F$ 的值，则枚举 $l,k$ 即可做到 $\mathcal{O}(n^3)$ 转移。

考虑计数问题，什么情况会计重？序列 $1111$，操作 $[1,2],[3,4]$ 和操作 $[1,4]$ 会被认为不同方案，而实际上最终得到的 $a$ 序列是一致的。处理很简单，我们将 $v^{(\rightarrow)}_{i,j}/v^{(\leftarrow)}_{i,j}$ 合法的条件改的更为严格：

这样子使得我们枚举的每个 $\rightarrow\leftarrow$ 区间都是在所有最终 $a$ 序列相同的方案中取到了分段更多的那个，从而构成了双射，同理定义 $g_r$ 可以一模一样地直接计数（区间全零的情况只能转移一次）。

这样子即提出了 $\mathcal{O}(n^3)$ 的做法。考虑优化：我们求出 $(\rightarrow)_i$ 为最大的 $j$ 使得 $v^{(\rightarrow)}_{i,j}$ 有意义，同理有 $(\leftarrow)_i$，显然 $k$ 可以进行转移的必要条件是 $k\in[l,r]\cap[(\leftarrow)_r,(\rightarrow)_l]$，然后只需要判断 $v_{l,r}(k)=v^{(\rightarrow)}_{l,k}+v^{(\leftarrow)}_{r,k}-a_k$ 与 $0$ 的大小关系。

发现每一个 $i\in[l,r]$ 的 $a_i$ 对 $v_{l,r}(k)$ 的贡献为 $(-1)^{k-i}a_i$，从而有 $v_{l,r}(k)$ 在 $k$ 为奇数/偶数时全相同，故在区间 $[l,r]\cap[(\leftarrow)_r,(\rightarrow)_l]$ 区间中有全体奇数/偶数均可转移。对于 $[l,r]$ 是否可以全零也仅需判断区间中任意一个 $k$ 是否满足条件即可。

故仅需快速计算 $\max\limits_{l\le i\le r,i\equiv p\pmod{2}}(-b_i)$ 和 $\sum\limits_{l\le i\le r,,i\equiv p\pmod{2}}\frac{1}{c_i}$，预处理即可。

复杂度为 $\mathcal{O}(n^2)$。