题解 | #换个角度思考#

void solve(){
    int n,m;cin>>n>>m;
    vpii v(n);
    for(int i=0;i<n;++i){
        int x;cin>>x;
        v[i]={x,i+1};
    }
    vector<array<int,4>> q(m);
    for(int i=0;i<m;++i){
        int l,r,k;cin>>l>>r>>k;
        q[i]={k,l,r,i};
    }
    sort(all(v));
    sort(all(q),[](auto&a,auto&b){return a[0]<b[0];});
    vi bit(n+1,0);
    auto add=[&](int i,int val){
        for(;i<=n;i+=i&-i)bit[i]+=val;
    };
    auto sum=[&](int i){
        int s=0;
        for(;i>0;i-=i&-i)s+=bit[i];
        return s;
    };
    vi ans(m);
    int p=0;
    for(int i=0;i<m;++i){
        int k=q[i][0],l=q[i][1],r=q[i][2],id=q[i][3];
        while(p<n&&v[p].fi<=k){
            add(v[p].se,1);
            ++p;
        }
        ans[id]=sum(r)-sum(l-1);
    }
    for(int i=0;i<m;++i)cout<<ans[i]<<endl;
}

import sys

MOD=1000000007
MOD2=998244353
def solve():
    n,m=int(next(it)),int(next(it))
    v=[[int(next(it)),i+1] for i in range(n)]
    q=[]
    for i in range(m):
        l,r,k=int(next(it)),int(next(it)),int(next(it))
        q.append([k,l,r,i])
    v.sort(key=lambda x:x[0])
    q.sort(key=lambda x:x[0])
    bit=[0]*(n+1)
    def add(i,val):
        while i<=n:
            bit[i]+=val
            i+=i&-i
    def sum(i):
        s=0
        while i>0:
            s+=bit[i]
            i-=i&-i
        return s
    ans=[0]*m
    p=0
    for i in range(m):
        k,l,r,id=q[i]
        while p<n and v[p][0]<=k:
            add(v[p][1],1)
            p+=1
        ans[id]=sum(r)-sum(l-1)
    for i in range(m):
        print(ans[i])

if __name__=="__main__":
    it=iter(sys.stdin.read().split())
    _=1
    #_=int(next(it))
    for __ in range(_):
        solve()