WC 之后 OI 复健的第一题。一开始啥都不会算，后面瞄了眼题解才往下推出来的。还是一道比较有意思的数据结构题。

设 表示 的 数量，即在数轴上 中初始有多少个球。设 表示当“小球进洞” 的过程运行到坐标 的时候，还剩下几个空位没有填。不难发现，将空位看成左括号，球看作右括号，小球进洞的过程非常类似括号匹配，而 就表示该括号序列匹配完前缀 之后栈中左括号的个数。

先考虑满足条件的 怎么算。考察数轴上一个 的位置 ，在做到 位置以前，一共有 个空位，做完之后变成了 个，即减少了 个空位，那这些空位中有多少个是坐标 的呢？考察区间 中 最小的点 （相同的取最靠左的那个）。显然如果 ，那么肯定没有在 以前的空位，否则就有 个球必须匹配到 或 左边。因为考虑在 位置不断加入球的过程， 会不断减小，当 时，显然 中已经没有空位了，且在此之前肯定还有空位，所以最后加入的那 个球就得放到 左边。而当 时， 之间显然也没有空位。综上所述，一个位置 的贡献为 。 这个式子容易用维护前缀最值的线段树维护。

再考虑 怎么算。因为一个空位只会被装最多一个球，我们直接考虑什么样的空位会被装球。对于位置 ，需要存在 满足 ，即 。那么，在某个时刻 (即考虑了所有 的球之后)，位置 还是空的当且仅当 且不存在 。

我们考虑把所有 的球都放进去之后的空位序列 ，显然满足条件的 是这个序列的一段后缀，而且该后缀的长度就是满足条件的球的个数，可以求 时顺便求出来，设其为 。所以我们考虑再用一棵维护后缀最值的线段树来维护 序列。可以通过在这个线段树上二分来找到 ，也就容易求出 ，即 了。

代码实现细节较多，需要特判 。笔者把两棵线段树分开写了，所以代码超长，放个提交记录在这里：https://loj.ac/s/1998086