树状数组、询问离线排序
我的想法是对询问离线，然后我们容易知道[l,r]的答案等于[1,r]的值减去[1,l-1]的值
所以把每次询问的两个端点都拉出来，标记好是左端点还是右端点，将每个询问的[1,l-1]和[1,r]答案记录下来
最后一次性输出差值即可。
复杂度O( (n+m) * logn)
貌似和大佬的离线有点不同 大佬的做法是顺便把a数组排序了，不过复杂度倒是一样的

#include<bits/stdc++.h>
using namespace std;
int c[1<<17];
int a[1<<17];
struct node
{
    int id,l,x,flag;
}q[1<<18];
int l[1<<17],r[1<<17];
void add(int x,int v){
    for(;x<=100000;x+=x&(-x)) c[x]+=v;
}
int get(int x){
    int ans=0;
    for(;x;x-=x&(-x)) ans+=c[x];
    return ans;
}
int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        int x,y,z;cin>>x>>y>>z;
        q[2*i-1]={i,x-1,z,0};///存询问的原位置、端点、查询值、是左端点还是右端点 左端点在存的时候直接减1
        q[2*i]={i,y,z,1};///flag为0表示左端点，1表示右端点
    }
    sort(q+1,q+2*m+1,[](node a,node b){
       return a.l<b.l; 
    });
    int k=1;
    for(int i=0;i<=n;i++){///l为1的时候 l-1为0  需要从0开始
        if(a[i])add(a[i],1);///不能处理0的情况 需要判断下
        while(q[k].l==i&&k<=2*m){
            int sum=get(q[k].x);
            if(q[k].flag==0) l[q[k].id]=sum;
            else r[q[k].id]=sum;
            ++k;
        }
    }
    for(int i=1;i<=m;i++) cout<<r[i]-l[i]<<endl;
    return 0;
}