abc427g
先离线下来，然后考虑统一处理所有询问，那么相当于每次把一个前缀 \(+A\)，把一个后缀 \(-B\)。那么你考虑用 fhq-treap 维护这个东西。显然这是一个平衡树有交合并板子，直接做就是 \(O(n\log^2 n)\) 的。
代码
CF1943D2
首先当存在一个 \(i\) 满足 \(a_{i-1}+a_{i+1}<a_i\) 即 \(a_{i+1}<a_i-a_{i-1}\) 时不合法。那么直接 dp 就是 \(f_{i,j,k}\) 表示填了 \(i\) 个，\(a_{i-1}=j,a_i=k\) 的方案数，应该可以优化一下做到 \(O(n^3)\) 同阶。
可以发现的是，不可能存在两个相邻的位置同时不满足限制。
设 \(f_{i,j}\) 表示前 \(i\) 个位置，\(a_i=j\) 且合法的方案数。直接从所有 \(f_{i-1,x}\) 转移过来显然会有部分不合法。此时你需要扣掉 \(f_{i-2,x}\times (k-x-j)\)，这相当于是扣掉了 \(i-1\) 不合法导致的多算。可以分别维护 \(f_{i,j}\times (k-j),f_{i,j}\) 的前缀和做到 \(O(n^2)\) 同阶。
代码