最优策略一定是选择一个柱子，不断的往上面添加，实在添加不了了就往前面的柱子进行添加。通过枚举柱子，二分答案，可以做到 \(O(nq\log^2 V)\)。
注意到二分答案时，我们相当于拖了一个尾巴 \((x,x/2,x/4,...)\)，我们设它为 \(c\)，对应柱子为 \(i\)，那么代价就是 \(\sum \limits_{j=0}\max(c_j-a_{i-j},0)\)。但是从实际情况来看，我们只会修改一个后缀，这是由于一开始就满足 \(a_i \times 2\geq a_{i+1}\)。而这个后缀的长度是 \(O(\log V)\) 级别的，那么我们可以通过枚举一个 \(k\)，也就是作用长度，来消除 \(\max\)。
具体的，若 \((i,k)\) 可以成为 \(M\) 的决策，当且仅当：
- \(a_{i-j}\lt c_j, \forall 0\leq j\lt k\)。
- \(a_{i-k}\geq c_k\)。
此时可以贡献的 \(M\) 的范围必然是一个区间，对应的代价就是 \(\sum \limits_{j=0}^{k-1}c_j-a_{i-j}\)。
观察这个代价，对于同一个 \(k\)，对于一个 \(M\) 来说最优秀的 \(i\) 必然是确定的，那么我们只需要对于每个 \(k\) 维护 \(O(n)\) 个情况的分段函数，那么就能在 \(O(\log V\log n)\) 的时间复杂度下找到指定 \(M\)，结合外层 \(O(q\log V)\) 个询问，做到 \(O(q\log^2 V\log n )\)。
二分和枚举 \(k\) 的复杂度必然不能省的，考虑在连续段上找到 \(M\) 对应位置的这个 \(O(\log n)\) 上下手，我们可以同时对所有询问进行二分，然后将他们询问的 \(M\) 排序后在这 \(k\) 个分段函数上从左往右扫即可做到 \(O(n\log ^2 V)\)。
标签：二分,柱子,CF2057F,log,lt,枚举,添加 From： https://www.cnblogs.com/xcyyyyyy/p/18655276