题解：P3285 [SCOI2014] 方伯伯的OJ

· · 题解

主流做法是动态开点的平衡树 / 线段树，但这里介绍一种基于分类的平衡树做法（非动态开点）。

思路来源：@kczno1 的 题解。

\bf Solution

Part 1

所有用户可以被分为三类：\bf\small A. 上次操作是 2 操作的；\bf\small B. 在中间没有经历过 2, 3 操作的；\bf\small C. 上次操作是 3 操作的。

初始时所有用户都在 \bf\small B 集合中。对用户 x 进行 2 操作时，把 x 从原集合中删除，加入到 \bf\small A 中；对用户 x 进行 3 操作时，把 x 从原集合中删除，加入到 \bf\small C 中。

Part 2

具体而言，维护三棵平衡树，分别表示 \bf\small A,B,C 集合。平衡树的中序遍历即为排名。平衡树中的每个元素维护其 键值、编号（外加子树大小等其它平衡树自带信息）。

其中的键值，定义如下：

这样定义的键值，既维护了有序性，又可以得知元素所在集合。

与此同时，再维护 编号所对应的键值，以便可以根据给出的编号，访问其在平衡树中的位置。可以用哈希表 / 平衡树。方便起见，代码里用 STL 中的 map 实现。

显然 \bf\small B 中元素过多，不能直接记录所有元素。我们可以取其补集，即 只记录被删除的元素。

Part 3

对于前三种操作，在 map 中用编号查到键值，在平衡树中查找到对应元素修改。

对于操作 4，若答案在 \bf\small A 或 \bf\small C 中很好做，但由于 \bf\small B 记录的是补集，答案在 \bf\small B 中较为难求。

答案一定在某段区间 (L,R) 中，L,R 是算上 0 和 n+1 后连续的两个被删除的元素。记 g(x) 表示 原集合 \bf\small B 中满足 t\in[1,x] 的 t 的个数，有 g(L)<\text{rank}<g(R)。在平衡树上二分求得最大的 x 满足 g(x)<\text{rank} ，可以算出答案。

实现时发现操作 4 在 \bf\small B 中求得的答案可能被改变了编号。再开一个 map，记录初始编号为 x 的数现在的编号即可。

\bf Code

洛谷 / LibreOJ

使用 FHQ-Treap 实现。题解中的 \bf\small A,B,C 集合分别对应代码中的 \bf\small U,P,D 平衡树。