换个角度思考

Problem:

n个数，询问[l,r]区间有几个数小于等于k，输出个数。

Solution：

树状数组，离线处理，n个数从小打到排序，m个询问按k从小到大排序，每次查询前都将小于等于k的数插入到该数位置上去，然后查询[l,r]区间有几个数就好了。
（1）由于排序了，所以可以保证树状数组中所有的数都是小于等于k的
（2）由于我们是把数相应位置插入到树状数组，以表示该位置上面有一个数，所以查询[l，r]区间有几个数就可以查询出答案。

#include
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define _for(i,s,t) for(int i=s;i<t;i++)
#define _rof(i,s,t) for(int i=s;i>t;i--)
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define per(i,s,t) for(int i=s;i>=t;i--)
#define Ri(x) scanf("%d",&x)
#define Rii(x,y) scanf("%d%d",&x,&y)
#define INF 0x3f3f3f3f
using namespace std;
templateinline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
typedef long long ll;
const int maxn = 1e5 + 10;
int c[maxn];
ll ans[maxn];
struct A{
    int v,i;
    friend bool operator < (A a1,A a2){
        return a1.v < a2.v;
    }
}a[maxn];
struct Q{
    int l,r,k,i;
    friend bool operator < (Q q1,Q q2){
        return q1.k < q2.k;
    }
}q[maxn];
int lowbit(int x){
    return x & (-x);
}
void add(int x,int v){
    while(x < maxn){
        c[x] += v;
        x += lowbit(x);
    }
}
ll query(int x){
    ll res = 0;
    while(x > 0){
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}
int main(){
    IOS;
    int n,m,v;
    cin>>n>>m;
    rep(i,1,n){
        cin>>a[i].v;
        a[i].i = i;
    }
    sort(a + 1,a + 1 + n);
    rep(i,1,m){
        cin>>q[i].l>>q[i].r>>q[i].k;
        q[i].i = i;
    }
    sort(q + 1,q + 1 + m);
    int inx = 1;
    rep(i,1,m){
        while(inx = a[inx].v){
            add(a[inx].i,1);
            inx ++;
        }
        ans[q[i].i] = query(q[i].r) - query(q[i].l - 1);
    }
    rep(i,1,m){
        cout<<ans[i]<<endl;
    }
    return 0;
}
/**
Problem:
    n个数，询问[l,r]区间有几个数小于等于k，输出个数。
Solution：
    树状数组，离线处理，n个数从小打到排序，m个询问按k从小到大排序，每次查询前都将小于等于k的数插入到该数位置上去，然后查询[l,r]区间有几个数就好了。
    （1）由于排序了，所以可以保证树状数组中所有的数都是小于等于k的
    （2）由于我们是把数相应位置插入到树状数组，以表示该位置上面有一个数，所以查询[l，r]区间有几个数就可以查询出答案。 
*/