整体二分总结

模板题题意：给定一个数组，m个询问，每次询问在数组l~r区间内第k大的数值是多少

（1）想到对于每个查询暴力排序查找，时间复杂度太大了

（2）把每个询问在线去做n^2的时间复杂度

引入整体二分：

整体二分的原理就是：把所有询问离线一起去找，而不是一个一个找浪费时间。所以要把a数组按数值（a）排序

每次递归，把询问和定值都分成两部分，把定值（排序后）砍半，放到树状数组里，这些是整个定值区间的小的一半

遍历查询区间里的每个查询i（此时，它们的位置和编号可能已经不对应了）如果树状数组中i.l~i.r内的数量>=i.k,放入左组;否则，放入右组，k减去数量

就这样，每次左右两组再拼回q数组，清空树状数组，继续向下迭代，直到定值的范围为：i~i,那么此时查询范围里的所有查询的答案就都是i了

复杂度：O((n+q)log n log n)（树状数组logn,logn层，每次树状数组修改和遍历问题n+q)

模板