学习笔记（？）：一类查询 kth 的整体二分 trick

问题大概就是有若干次修改（也有可能没有）和若干次查询，查询形如查某个范围的 kth。

做法是，把可能成为答案的候选集合按照权值大小排序。询问集合可以不用管顺序。然后开始二分。

我们令 solve(l,r,L,R) 表示第 \(l\) 到 \(r\) 个询问的 kth 一定在候选序列的第 \(L\) 到 \(R\) 个数。此时我们令把 \([L,R]\) 均匀分成两部分，然后把左边一部分塞入某个数据结构，然后再对于 \(l\) 到 \(r\) 每个查询，求出有数据结构内有多少个元素能对它产生贡献。如果少于 \(k\) 个，则其答案明显在右半，此时把 \(k\) 减去贡献数，并将其标记为 B 类。否则答案在左半，直接标记为 A 类。最后再把 A 类统一移到所有 B 类的左边，然后两边递归计算。可以知道这样数据结构插入和查询次数都是 \(\mathcal O((n+q)\log n)\) 的。

然后你发现这是个万金油 trick 啊，很多题都可以直接无脑套。