P3834 （靜態區間第k大，整體二分）

題意：

給定長度爲n的序列a，m次詢問，每次詢問給出L,R,k，要求計算[L,R]的第k小數

數據範圍：n,m<=2e5，-1e9<=a(i)<=1e9

解法：

整體二分的主要思想：
對需要在值域[l,r]內二分的所有詢問，共用一個二分，相比每個詢問於單獨二分，減少了二分總次數

整體二分是離線演算法。

需要注意的點：
二分的值域存在負數，二分需要寫mid=(l+r)>>1，而不能是mid=(l+r)/2
原因：
正數二分，[1,6]分爲[1,3]和[4,6]，因爲(1+6)/2=3
負數二分，[-6,-1]會分爲[-6,-3]和[-2,-1]，因爲(-6±1)/2=-3
發現負數二分，區間大小並不是均分的，正確的應該是[-6,-4]和[-3,-1]

因爲多了一個符號，"向下取整"變成"向上取整"了，所以會錯
正確做法是用位運算>>1，這樣就對了（負數是對二補數右移，而正數的二補數就是原碼，不一樣）

ps：
利用樹狀陣列離線的演算法，好像常常會將BIT存值變爲BIT存下標。

code：

#include<bits/stdc++.h>
using namespace std;
const int maxm=2e5+10;
struct Q{
    int l,r,k,op,id;
}q[maxm<<1],q1[maxm<<1],q2[maxm<<1];//q1:[l,mid],q2:[mid+1,r]
int cnt;
int ans[maxm];
int n,m;
//BIT
int c[maxm];
int lowbit(int i){
    return i&-i;
}
void add(int i,int t){
    while(i<maxm){
        c[i]+=t,i+=lowbit(i);
    }
}
int ask(int i){
    int ans=0;
    while(i){
        ans+=c[i],i-=lowbit(i);
    }
    return ans;
}
//
void solve(int l,int r,int L,int R){
    if(L>R)return ;
    if(l==r){
        for(int i=L;i<=R;i++){
            if(q[i].op==2){
                ans[q[i].id]=l;
            }
        }
        return ;
    }
    int mid=(l+r)>>1,cnt1=0,cnt2=0;
    for(int i=L;i<=R;i++){
        if(q[i].op==1){//number
            if(q[i].l<=mid){
                add(q[i].id,q[i].r),q1[++cnt1]=q[i];
            }else{
                q2[++cnt2]=q[i];
            }
        }else{//query
            int x=ask(q[i].r)-ask(q[i].l-1);
            if(x>=q[i].k){
                q1[++cnt1]=q[i];
            }else{
                q[i].k-=x;
                q2[++cnt2]=q[i];
            }
        }
    }
    for(int i=1;i<=cnt1;i++){//clear BIT
        if(q1[i].op==1)add(q1[i].id,-q1[i].r);
    }
    for(int i=1;i<=cnt1;i++){
        q[L-1+i]=q1[i];
    }
    for(int i=1;i<=cnt2;i++){
        q[L+cnt1-1+i]=q2[i];
    }
    solve(l,mid,L,L+cnt1-1);
    solve(mid+1,r,L+cnt1,R);
}
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&x);
        q[++cnt]={x,1,0,1,i};
    }
    for(int i=1;i<=m;i++){
        int l,r,k;scanf("%d%d%d",&l,&r,&k);
        q[++cnt]={l,r,k,2,i};
    }
    solve(-1e9,1e9,1,cnt);
    for(int i=1;i<=m;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}