正义打败邪恶！CDQ 分治与整体二分碾压树套树与分块。

· · 题解

本题有一个非常好的性质：没强制在线。所以我们可以离线下来搞。

具体怎么做呢？本题的核心就是点修、区间第 k 大、区间求排名。我们知道，CDQ 分治和整体二分分别可以很方便并且快速地解决区间排名以及区间第 k 大问题。那么我们分别用这两种算法做不同的操作就可以了。

还剩下前驱和后继，怎么处理？某个数的前驱，可以先算出严格小于这个数的数量 k，然后求第 k 大。某个数的后继，可以算出小于等于这个数的数量 k，然后求第 k + 1 大。

这时我们发现，我们需要将这两个操作组合起来。我们可以把询问拆开，先跑 CDQ 分治，得到 k，然后再跑整体二分，得到最后的结果。

实现起来细节不特别多，主要是主函数中拼接操作的部分不怎么好写。

但是跑起来飞快，没怎么卡常就跑到最优解第二页。

代码