牛客小白月赛9 E、换个角度思考（离线+树状数组）

一道非常好的题目
题目链接
题目大意：
输入：
5 1
1 2 3 4 5
1 5 3
输出：
3

总体思路：
这题用 离线+树状数组 来写最简单。我们可以发现每一次查询会有两个变量，一个是区间左右的整体，另一个是K值。所以我们可以固定其中一个值来求另一个值。

方法一：
在保证当前所有数都是小于等于K的情况下询问区间[l, r]有多少个数。
我们先将ai和K从小到大排序，将ai对应的位置加1，每次查询区间[l, r]有多少个数小于等于K，只需要查区间[l-1, r]存在的数的个数。
代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,q;
int c[100005];
struct ty{
    int x;
    int id;
};
ty a[100005];
struct node{
    int l,r;
    int k;
    int id;
    int val;
};
node b[100005];
bool cmp1(ty a1,ty a2){
    if(a1.x!=a2.x) return a1.x<a2.x;
    return a1.id<a2.id;
}
bool cmp2(node a1,node a2){
    return a1.k<a2.k;
}
bool cmp3(node a1,node a2){
    return a1.id<a2.id;
}
int lowbit(int i){
    return i&(-i);
}
void add(int i,int x){
    while(i<=n){
        c[i]+=x;
        i+=lowbit(i);
    }
    return ;
}
int sum(int i){
    int s=0;
    while(i>0){
        s+=c[i];
        i-=lowbit(i);
    }
    return s;
}
int main(){
    scanf(" %d %d",&n,&q);
    for(int i=1;i<=n;i++) {
        scanf(" %d",&a[i].x);
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp1);
    for(int i=1;i<=q;i++){
        scanf(" %d %d %d",&b[i].l,&b[i].r,&b[i].k);
        b[i].id=i; b[i].val=0;
    }
    sort(b+1,b+1+q,cmp2);
    int inx=1;
    for(int i=1;i<=q;i++){
        int t=b[i].k;
        for(int i=inx;i<=n&&a[i].x<=t;inx++,i++){
            add(a[i].id,1);
        }
        b[i].val=sum(b[i].r)-sum(b[i].l-1);
    }
    sort(b+1,b+1+q,cmp3);
    for(int i=1;i<=q;i++) printf("%d\n",b[i].val);
    return 0;
}

方法二：
在保证当前数都是[l, r]区间的情况下查询小于等于x的数字个数。
们可以离线的时候把[l, r]区间转化为[1,l-1]和[1,r]两个区间，这样子问题就变成，在前若干个数字里面求小于等于K的数字个数。于是我们可以用一个值域树状数组统计每一个值的当前区间出现了多少次。先将每次查询的左右端点和K分别存入一个pair变量中，再用map对应每一个pair前面有多少个小于等于K的数，最后map[pair<r, k>]-map[pair<l-1, k>]就是每个区间的值！
实现代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int ,int >  P;
int n,q;
int d[100005];
map<P,int > a;
struct ty{
    int l,r;
    int k;
};
ty b[100005];
int c[100005];
int lowbit(int i){
    return i&(-i);
}
void add(int i,int x){
    while(i<=n){
        c[i]+=x;
        i+=lowbit(i);
    }
    return ;
}
int sum(int i){
    int s=0;
    while(i>0){
        s+=c[i];
        i-=lowbit(i);
    }
    return s;
}

int main(){
    scanf(" %d %d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf(" %d",&d[i]);
    }
    for(int i=1;i<=q;i++) {
        scanf(" %d %d %d",&b[i].l,&b[i].r,&b[i].k);
        P p; 
        p.first=b[i].l-1; p.second=b[i].k; a[p]=0;
        p.first=b[i].r; p.second=b[i].k; a[p]=0;
    }
    map<P,int >::iterator it;
    int index=1;
    for(it=a.begin();it!=a.end();it++){
        int t=it->first.first;
        //cout<<"t="<<t<<"\n";
        if(index<=t){
            for(int j=index;j<=t&&j<=n;j++,index++){
                //cout<<"j="<<j<<"\n";
                add(d[j],1);
            }
        }
        int temp=sum(it->first.second);
        //cout<<"temp="<<temp<<"\n";
        it->second=temp;
    }
    for(int i=1;i<=q;i++){
        P p1,p2;
        p1.first=b[i].l-1; p1.second=b[i].k;
        p2.first=b[i].r; p2.second=b[i].k;
        printf("%d\n",a[p2]-a[p1]);
    }
    return 0;
} 

总结：当我们查询时出现两种类型的变量时，我们就可以采用离线化的处理方式，来确实其中一种变量，来查询第二种变量。（实测第一种用法比第二种快很多）。