很牛的题，想到了在笛卡尔树上统计，没想到可以做区间 dp。
把原序列 \(f\) 建一个笛卡尔树，会发现有 \(f'=\sum_{j} f_j\times(sz_j-1)\)。具体而言，遍历这棵笛卡尔树，当前节点的子树代表的区间为 \([l,r]\)，最小值位置在 \(k\)。发现 \(f_k\) 对 \([l,r]\) 里的每个 \(f'\) 分别有贡献 \(f_k\times(r-l)\)，\([l,r]\) 里的 \(f'\) 全局减去这个贡献后，会发现 \(f'_{[l,k]}\) 会只与 \(f_{[l,k-1]}\) 有关，\(f'_{[k+1,r]}\) 会只与 \(f_{[k+1,r]}\) 有关，然后继续往下递归算贡献，一种合法的 \(f\) 构造方案会让所有 \(f'\) 都在遍历完毕后被减成 \(0\)。
考虑将这棵笛卡尔树自下往上遍历，这是一个区间合并的过程，所以考虑区间 dp。设 \(dp(l,r,x)\) 表示 \([l,r]\) 内的所有 \(f'\) 全局减 \(x\) 后是否能构造出对应的 \(f\) 方案。转移也可以写出来：\(dp(l,r,x)=\bigvee_{k} dp(l,k,x+f_k\times (r-l)) \wedge dp(k+1,r,x+f_k\times (r-l))\)。需要枚举 \(x\) 和 \(f_k\)，时间复杂度 \(O(n^2V^2)\)。
显然是过不去的，注意到 \(dp(l,r,x)\) 成立时，\(dp(l,r,x-(r-l))\) 时直接把 \(dp(l,r,x)\) 的 \(f_k+1\) 代成 \(f_k\) 就成立，所以我们对于每个 \(x \bmod (r-l)\) 只需要知道 \(x\) 的最大值即可。不妨重设状态 \(dp(l,r,x)\) 表示 \([l,r]\) 内的所有 \(f'\) 全局减 \(y\equiv x\pmod {(r-l)}\) 后能构造出对应的 \(f\) 方案的最大 \(y\)。经过一些数论操作后可以做到 \(O(n^5)\)，由于常数很小就过了。
套路题，在周末返校的路上想明白了。
操作差分下来，离线扫描 \(n\)。问题变成现在有操作序列，每次询问进行一个前缀的操作后（在原题中即在时间轴上的前缀），栈里某个区间的和。
对于一段操作序列的信息，只需要存进行完当前这一段的操作过后，这一段操作剩下的栈长啥样，以及需要删这一段操作的之前的操作的栈里多少个数。要维护一个 vector 一个 int，线段树维护有点过于复杂了，考虑分块。要支持单点修，每次单点修时暴力重构即可。询问时需要二分的块分配得好的话可以做到 \(O(n\sqrt n+n\log n)\)。关于 segt beats 做法，我不会。
扫描线，事实上并不会出现一个人在排与不排之间反复横跳的情况，所以直接维护即可，很没意思。
做不来啊，这个 trick 真是神仙。
题面转化就不说了。从大到小扫描 \(x\)，每次看一下哪些询问满足条件，如果满足就记一下答案然后把它踢出去。
这个是不好维护的，然而发现当 \([l_1,r_1]\) 被 \([l_2,r_2]\) 包含时，\(\mathrm{Ans}([l_1,r_1])\le \mathrm{Ans}([l_2,r_2])\)。每次看哪些询问满足条件时只需要看没被其他区间包含的询问区间即可。这个时候发现区间之间不包含可以直接线段树维护区间加全局 \(\max\) 了。复杂度就是 \(O(n\log n)\)。