Envío 5622

Código

#include <bits/stdc++.h>
using namespace std;

void _print() { cerr << "]" << endl; }
template<typename T, typename... V>
void _print(T t, V... v) { cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...); }

#ifdef LOCAL
    #define dbg(x...) cerr << "[" << #x << "]: ["; _print(x)
#else
    #define dbg(x...)
    #define endl '\n'
#endif
#define ll long long
#define sz(x) int(x.size())

int S, n, q;

struct query {
    int l, r, idx, vx;
    query(int _l, int _r, int _idx, int _vx): l(_l), r(_r), idx(_idx), vx(_vx) {}

    bool operator < (const query &x) const {
        if (l / S != x.l / S) return l / S < x.l / S;
        return (l / S & 1) ?  r < x.r: r > x.r;
    }
};

vector<query> qu;
vector<int> ans, arr;
map<int, int> mp;

void add(int x) {
    mp[arr[x]]++;
}

void del(int x) {
    mp[arr[x]]--;
}

int get_ans(int x) {
    return mp[x];
}

void mo_s() {
    S = sqrt(n);
    sort(qu.begin(), qu.end());
    ans.resize(q);
    int l = 0, r = -1;
    for (query &it: qu) {
        while (r < it.r) add(++r);
        while (l > it.l) add(--l);
        while (r > it.r) del(r--);
        while (l < it.l) del(l++);
        ans[it.idx] = get_ans(it.vx);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    arr.resize(n);
    for (int &i : arr) cin >> i;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int l, r, x; cin >> l >> r >> x;
        qu.push_back({l, r, i, x});
    }
    mo_s();
    for (int &i : ans) cout << i << endl;
    return 0;
}