OI Wiki 已经讲的非常好了:https://oi-wiki.org/misc/parallel-binsearch/

 这里做简单的记录.

使用前提：询问具有单调性。

思想：利用分治的思想每次处理多个询问.

例如:

1.多次询问整体第k大.

2.多次询问区间第k大。

如何实现询问区间第k大？ 

答：原理还是一样的，只不过之前只需要知道全局值域在[l,r]中的数的个数.现在我们需要知道某个区间中值域在[l,r]中的数的个数

我们需要套一个树状数组,

分治的时候不仅维护 【答案可能在[l,r]中】 的询问。同时维护【值域在[l,r]的 原序列中的数】. 将它们插入树状数组, 这样我们可以利用树状数组统计任意区间中值域在[l,r]中的数的个数.最后记得撤销树状数组的内容.

3.带修改多次询问区间第k大.

问题在于：现在需要动态做修改，那么不能单纯将插入值和询问分开处理。因为一个修改会影响它之后的查询.

这有点像： 先区间加后区间询问 与 区间加区间询问混合 的区别。 前者差分前缀和即可，后者要树状数组.

思想：在保证分治值域的同时，也保证操作的时间相对顺序正确

不妨将修改看成删除与增添。将数组初始化, 查询和插入都看成操作。一起分治。所以大家一起公用一个全局数组node[maxn * 3].

 在分治的过程的时候，维护值域[l,r] 再维护[L,R]代表操作数组中处理的区间。那再以值域为关键字分治的时候，操作的时间相对顺序是不变的，所以保证最后答案是正确的。

写代码的时候也要注意一定是所有操作一起搞。边分数组，边对树状数组做操作