题解：P11286 [COTS 2017] 盗道 Krimošten

本题解（基本）思路来自于 https://www.luogu.com.cn/article/6kmsqopa ，但维护方法略有不同。

为了方便表述，我们认为所有盗贼同时进行盗窃（且房子的 $a_i$ 始终不变），时刻 $i$ 盗窃第 $i$ 个房子。

考虑对所有询问离线，那么本题等价 ：对于每个时刻，将所有小于 $a_i$ 的点加一，将所有大于 $a_i$ 的点减一，查询在 $l_i$ 时刻等于 $x_i$ 的点在 $r_i$ 时刻的值。

容易想到用平衡树维护。在时刻 $i$ 对于所有 $l_j = i$ 的询问 $j$ ，将 $x_j$ 加入平衡树，记录加入平衡树的节点编号 $p_j$。每次盗窃的时候将严格小于 $a_i$ 的部分全部减一，严格大于 $a_i$ 的部分全部加一。一个询问的答案即为其对应节点 $p_j$ 在 $r_j$ 时刻的值。

具体维护上需要注意：

如果平衡树写相同权值节点合并的话，可以使用并查集等数据结构维护一个节点最终指向的节点（即为，当在平衡树上合并两个节点 $x,y \rightarrow x$ 的时候，将 $y$ 向 $x$ 节点合并。

亦可以在打 tag 的时候只对严格小于和严格大于 $a_i$ 的部分打tag，实现也很方便。

复杂度 $O(m \log m+n\log m)$ ，可以通过此题。

本人平衡树代码过于丑陋，不予展示。

updata on 2024/11/21 更新了一些实现上的细节。