P13272
lsj2009
·
·
题解
考虑答案形式，一次操作 (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}<a_k 则最终 k 不能为 [l,r] 最终非零位。
-
若 v^{(\rightarrow)}_{l,k}+v^{(\leftarrow)}_{r,k}=a_k 则最终 [l,r] 全零。
-
若 v^{(\rightarrow)}_{l,k}+v^{(\leftarrow)}_{r,k}>a_k 则最终 k 可为 [l,r] 最终非零位。
将 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} 合法的条件改的更为严格：
- 若途中出现 a_k=a_{k\pm 1} 即不合法。
这样子使得我们枚举的每个 \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)。