换个角度思考

题意

给定序列，多次查询，每次查询一个区间内小于某个数的个数。

思路

题目疯狂暗示换个角度思考🤔，我就先姑且试试。开始先想到的是用一堆桶存对应数的下标，这样对于一次查询 我们只需要在那些<=k的桶里找下标处于 的个数，考虑到有多个查询，我们可以利用单调性先将查询排个序，离线处理。接下来就是数数的问题了，开始想的是用差分和前缀和，后来想想好像不太行（每得出一次查询都是），由于点进题目之前瞄到了一眼数状数组，遂尝试了一波，可（大雾）。

复杂度

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define db double
#define mp make_pair
#define fi first
#define se second
#define de(a) cout << #a << " = " << a << endl

const int maxn = 1e5 + 10;

int ans[maxn], c[maxn];

struct Query{
    int l, r, val, id;
    bool friend operator < (Query a, Query b){
        return a.val < b.val;
    }
};

int n, m;
Query q[maxn];
vector<int> num[maxn];



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

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

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int t;
        cin >> t;
        num[t].pb(i);
    }

    for(int i = 0; i < m; i++){
        cin >> q[i].l >> q[i].r >> q[i].val;
        q[i].id = i;
    }
    sort(q, q + m);
    for(int i = 1, idx = 0; i < maxn; i++){
        while(idx < m && q[idx].val < i){      //这里是while, 不是if QAQ
            //de(q[idx].val);
            ans[q[idx].id] = f(q[idx].r) - f(q[idx].l - 1); 
            idx++;
        }
        for(int v : num[i]){
            add(v, 1);
        }
    }

    for(int i = 0; i < m; i++){
        cout << ans[i] << endl;
    }


    return 0;
}