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

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

part 1 本题思路

为了方便表述，我们认为所有盗贼同时进行盗窃（且房子的 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 更新了一些实现上的细节。