题解 | 换个角度思考喵

发现这个信息线段树不好维护喵～小男娘也不会喵～

但是发现可以离线喵～从小到大依次处理数字和询问喵～于是问题就变成了单点加一区间求和喵～直接变成树状数组板子了喵～

#include <iostream>
#include <vector>
#include <array>

using namespace std;

int n;
int m;
const int MAXI = 1e5;
array<vector<int>, MAXI + 1> aPos;
// idx, l, r
array<vector<array<int, 3>>, MAXI + 1> queries;
vector<int> res;

array<int, MAXI + 1> szsz;

void Addi(int x) {
    while (x <= MAXI) {
        szsz[x]++;
        x += x & -x;
    }
}

int Pre(int x) {
    int res = 0;
    while (x > 0) {
        res += szsz[x];
        x &= x - 1;
    }
    return res;
}

int Sum(int l, int r) {
    return Pre(r) - Pre(l - 1);
}

void Solve() {
    cin >> n >> m;
    res.resize(m);
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        aPos[a].push_back(i);
    }
    for (int i = 0; i < m; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        queries[k].push_back({i, l, r});
    }
    for (int i = 1; i <= MAXI; i++) {
        for (int pos : aPos[i]) {
            Addi(pos);
        }
        for (auto query : queries[i]) {
            res[query[0]] = Sum(query[1], query[2]);
        }
    }
    for (int x : res) {
        cout << x << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
}