$30$ 分 WA+TLE

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

const int N = 1e5 + 5;
int a[N], cnt[N], sizb, res[N];
struct query {
    int l, r, x, id;
    bool operator < (const query &o) const {
        if (l / sizb != o.l / sizb)
            return (l / sizb) < (o.l / sizb);
        if ((l / sizb) % 2 == 0)
            return r < o.r;
        else
            return r > o.r;
    }
} q[N];
map <int, int> mp;

void sol() {
    mp.clear();
    int n, m, cur = 0, l = 1, r = 0;
    cin >> n;
    sizb = sqrt(n);
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mp[a[i]]++;
    }
    for (auto &p : mp)
        p.second = ++cur;
    for (int i = 1; i <= n; i++)
        a[i] = mp[a[i]];
    cin >> m;
    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 + m + 1);
    for (int i = 1; i <= m; i++) {
        while (q[i].l < l)
            cnt[a[--l]]++;
        while (q[i].l > l)
            cnt[a[l++]]--;
        while (q[i].r < r)
            cnt[a[r--]]--;
        while (q[i].r > r)
            cnt[a[++r]]++;
        res[q[i].id] = cnt[q[i].x];
    }
    for (int i = 1; i <= m; i++)
        cout << res[i] << '\n';
}

int main() {
    int T;
    cin >> T;
    while (T--)
        sol();
}