题解：AT_arc168_f [ARC168F] Up-Down Queries

我将详细揭秘这为什么是一个难度适中的 CSP 模拟赛的题。

为了方便我们 $a_i\gets m-a_i$。

我们从左往右扫，维护一些区间 $[0,x]$ 表示将这个区间的值 $+1$。对于一个需要 $-1$ 的区间 $(y,m]$，如果 $x>y$ 那么我们可以交换 $x,y$。那么对于所有区间操作一遍就相当于把 $\max x>y$ 时把 $y$ 换进去 $\max x$ 换出来，即加入 $y$ 并删除 $\max x$。当然我们还需要加入另一个 $y$，即加入的区间本身。用堆维护容易做到单次询问 $O(n\log n)$。

我们现在允许一些位置不干活，然后扫到 $i$ 的时候只有堆大小 $>i$ 才弹出最大值（或者说，随便弹出一个并最小化答案），考虑如何加入一个数并维护最终在堆里的数。我们先强行加入，如果有一个位置爆了（即前缀元素数量大于前缀长度），找到最前面的这个位置并删除前缀 $\max$。对于之后的位置，我们的操作没有使任何东西变大，所以放弃原来的方案弹出新的元素一定是不划算的。

注意到最终结果和加入顺序无关，且加入的影响是 $O(1)$ 的，所以删除的影响肯定也是 $O(1)$ 的。具体地，如果删除的元素在最终的堆里，我们直接删除后找到最后一个塞满的位置之后的最小的元素加入即可。

这些东西都可以用线段树维护，复杂度 $O((n+q)\log n)$。