题解 | 换个角度思考

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) x&-x
const int N=1e5+10;
int a[N],sum[N];
struct point
{
    int l,r,k,id,jg;
}e[N];
struct node
{
    int z,pos;
}b[N];
bool cmp(const point&x,const point&y)
{
    return x.k<y.k;
}
bool cmp1(const node&x,const node&y)
{
    return x.z<y.z;
}
void updata(int x)
{
    while(x<N)
    {
        sum[x]++;
        x+=lowbit(x);
    }
}
int getdata(int x)
{
    int res=0;
    while(x>0)
    {
        res+=sum[x];
        x-=lowbit(x);
    }
    return res;
}
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i].z=a[i];
        b[i].pos=i;
    }
    sort(b+1,b+1+n,cmp1);
    for(int i=1;i<=m;i++)
    {
        cin>>e[i].l>>e[i].r>>e[i].k;
        e[i].id=i;
    }
    sort(e+1,e+1+m,cmp);
    int now=1;
    for(int i=1;i<=n;i++)
    {
        //cout<<b[i].z<<" "<<e[now].k<<"\n";
        if(b[i].z<=e[now].k)
        {
            updata(b[i].pos);
        }
        else
        {
            e[now].jg=getdata(e[now].r)-getdata(e[now].l-1);
            now++;
            i--;
            if(now>m)break;
        }
    }
    while(now<=m)
    {
        e[now].jg=getdata(e[now].r)-getdata(e[now].l-1);
        now++;
    }
    sort(e+1,e+1+m,[](const point& x,const point& y){return x.id<y.id;});
    for(int i=1;i<=m;i++)
    {
        cout<<e[i].jg<<"\n";
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t__=1;
    //cin>>t__;
    while(t__--)
    {
        solve();
    }
    return 0;
}