Luogu7476 苦涩

题意：维护 个多重集 ，初始时均为空集。

支持下列操作：

• 向 中加入 。

• 记 ，对于 ，若 ，则从 中删去一个 。

• 查询 ，或指出 均为空。

，时限 。

---

使用标记永久化，在每个节点用一个堆维护标记。

进行操作 时，假设修改的是 ，先查询出 ，然后尝试删除。

下放区间 的标记时，若堆顶为 （由于此时 和 必然有交，堆顶不可能 ），则弹出，并将 重新加入到区间 中（相当于两个 操作）。

某次上述操作执行成功后，直接返回，因为 只会被删除一个。

此外，若区间 ，也无需操作。

其余情况，暴力递归。

---

下面证明复杂度。

我们发现，暴力递归的复杂度不会大于标记深度和，于是只考虑插入标记的操作，并统计其深度和。

每次 操作新建的标记的深度和显然为 。

在 操作中，只有与 部分相交的两个线段树节点可能产生 操作。增加的标记的深度和也是 。

复杂度均摊正确， 为 。