ABC388 题解
ABCDE+G，rk 371。
D
观察到几个性质：
- 一个人只会在成年的时候得到石头，在成年之后给出石头。
- 第 \(i\) 个人成年之后，他要给之后的每个人一个石头（除非用光了）。也就是说，假设成年时它的石头数量为 \(B_i\)，则最终他的石头数量为 \(\max(0, B_i - (n - i))\)。
因此我们只需计算每个人在成年时会得到几个石头。这等价于询问他之前的人中，有多少人的石头数量 \(> 0\)。计算的方法很多。我在第 \(i\) 个人成年后，把 \(B_i + i\) 放到一个小根堆中，这个数就表示他能给到第几个人。（\(+ i\) 是为了统一）。统计第 \(i\) 个人成年时能得到几个石头，就弹出小根堆中所有 \(< i\) 的值，之后小根堆的大小就代表他能获得的石头数量。时间复杂度 \(O(n \log n)\)，当然还有一些简单的线性做法。
不过这个做法还是稍微要点脑子，我也不保证我一定能想出来。我们有更直接的做法：直接模拟给石头的过程，用树状数组优化就行，只是码量略大。还是那句话：观察到的性质越多，代码就可以写得越简单。
E
结论：如果存在一个大小为 \(x\) 的匹配，那它一定可以表示为一个长为 \(x\) 的前缀和一个长为 \(x\) 的后缀匹配（即第 \(i\) 个元素匹配第 \((n - x + 1)\) 个元素）。
这个结论比较容易猜，但我不会严格证明。
有了这个结论之后，可以简单地用二分来得到答案。但实际上我们有线性做法，并且这个做法可以扩展到 G 的回滚莫队：
固定左端点 \(L = 1\)，右端点 \(R\) 从 \(1\) 开始向右扩展，每次扩展时尝试更新当前的最大匹配 \(cnt\) 的值，\(R\) 扩展到 \(N\) 时 \(cnt\) 即为答案。（起初 \(cnt = 0\)。）这个结论是此做法的基础：我们只要知道最大匹配的大小，就能确定它的形态（即哪个元素和哪个元素匹配），这样就不用去记录匹配的形态。\(R\) 扩展到 \(R + 1\) 时，判断 \(cnt\) 是否会 \(+1\)。我们只需判断 \(A_{cnt + 1} \le 2A_{R - cnt - 1}\) 是否成立即可。有一个 corner case：当 \(cnt\) 的大于区间长度的一半就不用尝试更新 \(cnt\) 了，因为此时 \(cnt\) 不会变大。
G
区间询问，不强制在线，我们可以考虑用莫队来解决。根据 E 的线性做法，已经知道如何 \(O(1)\) 扩展，但如何删除呢？我们发现，要判断删除一个端点后 \(cnt\) 会不会 \(-1\)，等价于判断：对于区间内长度为 \(cnt\) 的前缀和等长的后缀，前缀和后缀内的第 \(i\) 个数能否一一匹配，这似乎不太好维护。（实际上这可以转化为一个 RMQ 问题，见这篇题解。但能想到这个做法的话就不用莫队了）
但是我们还是能用莫队来做！对于这种扩展容易、删除困难的问题，可以用一种叫做“回滚莫队”的改版莫队来解决。这种算法可以在不能删除区间端点的情况下解决问题，并且时间复杂度和莫队一样都是 \(O(n \sqrt n)\)（假设询问次数 \(q\) 和序列长度 \(n\) 同阶，下同。）
还是把序列分成 \(B\) 块。对于每个询问，如果其左右端点在同一块，我们就暴力扩展处理，这样对于单个询问，时间复杂度是 \(O(n / B)\) （由于其左右端点在同一块，所以区间长度不超过 \(n / B\)。）否则，把询问按左端点所在的块分类，对于左端点在同一块的询问，我们一起处理。
具体而言，对于左端点在同一块内的询问，先按右端点大小从小到大排序。然后，还是用 \(L,R\) 和 \(cnt\) 表示当前处理的区间左右端点，和区间内最大匹配的大小。对于左端点在第 \(i\) 块的询问，初始化 \(L, R\) 为第 \(i\) 块的右端点，然后不断令 \(R\) 向右扩展。扩展到 \(R = j\) 时，如果有某个询问的左端点在第 \(i\) 块，而右端点为 \(j\)，我们就处理这个询问。此时，\(R\) 已经到位了，但左端点还在原位，那么我们让左端点向左扩展，直到其到位为止。由于一开始 \(L\) 在第 \(i\) 块的右端点，所以 \(L\) 一直往左移动就能到位。但移动之后，对于之后的询问，\(L\) 可能就在它的左端点的左边了，而我们又不能删除，那怎么办呢？这里就是回滚莫队的精髓了：在 \(L\) 移动之前，我们先记录下移动前的 \(cnt\)。移动之后，直接把 \(L\) 和 \(cnt\) 修改为原来的值，就可以 \(O(1)\) 地回到移动前的状态，这就是“回滚”。于是，对于每个询问，我们都能保证 \(L\) 在其左端点的右边，这就规避了删除操作。
时间复杂度分析：处理左端点在一个块内的询问时，\(R\) 是单调增的，最多移动 \(n\) 次；对于每个询问，\(L\) 最多移动 \(n / B\) 次。因此处理左右端点不同块的询问，时间复杂度为 \(O(nB + \dfrac{n^2}{B})\)，取 \(B = \sqrt{n}\) 最优，时间复杂度为 \(O(n \sqrt n)\)。而处理左右端点同块元素的时间复杂度是相同的，因此这就是回滚莫队的时间复杂度。
（回滚莫队练习题）「JOISC 2014 Day1」历史研究
这不是这场 ABC 的题，但刚学回滚莫队，把这道题就一起放这里了吧。
这道题扩展是容易的，因为序列中的数都是正数，所以一个数的重要值单调不降，整个区间的最大重要值也单调不降，因此每次更新一个数的重要值后，都可以尝试用它来更新区间的最大值。但删除是困难的，因为一个数的重要值单调不升，而原先的区间最大值变小之后难以快速更新。扩展容易删除难，这就是回滚莫队典型的应用场景。
在回滚莫队中，除了区间的扩展，还有一个重要的部分是回滚。这道题的回滚比 G 稍微复杂一些（但也还好）：扩展之后，重要值数组会更新。如果我们拷贝整个重要值数组，回滚的时候再赋值回来，时间复杂度接受不了。不妨用一个 vector 记录下将要扩展的区间的数当前的重要值，回滚的时候重新赋值就行了。