嘟嘟嘟

这个题可以单 $\log$。

默认大家会 $\log^3$ 做法。考虑我们是怎么加入一个元素的：把他加入某个数据结构，然后找到最深的子树内元素个数大于子树大小的节点，删除子树内最小的元素。

注意到我们只修改了两个元素，而且答案显然和加入顺序没关系，那么理论上我们删除一个在答案里的元素的时候也只会加回来一个。我们维护一个不在答案里的元素的数据结构，删除一个元素后显然只有所有祖先都没满的元素才能加回来，我们加回来最大的元素。

我们考虑在静态 toptree 上维护这个东西。我们维护在/不在界点路径上的 子树大小减子树元素个数 的最小值（这个肯定需要非负），同时维护是否取到两个最小值的四个状态的最大元素，这个显然是可以合并的。对于加入操作，我们可以顺便维护两个最深的最小值位置，然后在 DFS 序上使用线段树维护最小的已加入的元素。

这样我们就做到了单 $\log$ 并且还是在线的。code