题解 | 换个角度思考

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
const int mod = 998244353;
typedef long long ll;
typedef unsigned long long ull;
const ll INF = 2e9;
ll n,m;

ll ans[N];
struct Query
{
    ll l,r,x;
    int id;

}q[N];

struct Node
{
    ll v,idx;
}a[N];


bool cmp(Query a,Query b)
{
    return a.x<b.x;
}

bool cmp2(Node a,Node b)
{
    return a.v<b.v;
}



struct BIT {
    int n;
    vector<int> tr;

    BIT() {}
    BIT(int n) { init(n); }

    void init(int _n) {
        n = _n;
        tr.assign(n + 1, 0);
    }

    void add(int x, int v) {
        for (; x <= n; x += x & -x) tr[x] += v;
    }

    int sum(int x) {
        int res = 0;
        for (; x > 0; x -= x & -x) res += tr[x];
        return res;
    }

    int query(int l, int r) {
        if (l > r) return 0;
        return sum(r) - sum(l - 1);
    }
};




void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].v;
        a[i].idx = i;
    }

    sort(a+1,a+1+n,cmp2);
    
    BIT b1(N);
    
    for(int i=1;i<=m;i++)
    {
        cin>>q[i].l>>q[i].r>>q[i].x;
        q[i].id =  i;
    }

    sort(q+1,q+1+m,cmp);

    int idx = 1;
    for(int i=1;i<=m;i++)
    {
        while(idx<=n&&a[idx].v<=q[i].x)
        {
            b1.add(a[idx].idx,1);
            idx++;
        }   

        ans[q[i].id] = b1.query(q[i].l, q[i].r);
    }

    


    for(int i=1;i<=m;i++)
    {
        cout<<ans[i]<<'\n';
    }

    

    

}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();

    }


    return 0;
}

用的树状数组，加二次排序做的，由于求的值域是从1到x所以我们可以先讲a数组按照v大小排序，然后讲q也按照x的大小排序

，然后每次查询，讲小于等于x的所有a添加进树状数组中，然后求区间之和即可