P3834 （静态区间第k大，整体二分）_输入长为n的序列,m次询问,每次询问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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

---