换个角度思考

题解:主席树模板,树状数组也行

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;

int n,m,bit[MAXN],ans[MAXN];
struct Num{
    int x,id;
    bool operator<(const Num& obj)const
    {
        return x<obj.x;
    }
}a[MAXN];
struct Query{
    int l,r,k,id;
    bool operator<(const Query& obj)const
    {
        return k<obj.k;
    }
}q[MAXN];


inline int lowbit(int i){return i&(-i);}
void add(int i)
{
    while(i<=n){
        bit[i]++;i+=lowbit(i);
    }
}
int sum(int i)
{
    int res=0;
    while(i>0){
        res+=bit[i];i-=lowbit(i);
    }
    return res;
}


int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].x);
        a[i].id=i;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
        q[i].id=i;
    }
    sort(q+1,q+1+m);
    int it=1;
    for(int i=1;i<=m;i++)
    {
        while(a[it].x<=q[i].k&&it<=n){
            add(a[it].id);it++;
        }
        ans[q[i].id]=sum(q[i].r)-sum(q[i].l-1);
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}