rt,求hack。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;

const int N = 2e5 + 5;

int n, m, a[N], ans[N], cnt[N], blo, fkcnt[N];

#define get(x) (x / blo + 1)
#define getL(x) (max(1, (x - 1) * blo))

int maxn = 0;

struct Node
{
	int id, l, r, k;
	bool operator<(const Node& g) const
	{
		int gl = get(l), pl = get(g.l);
		if (gl ^ pl) return gl < pl;
		return (gl & 1 ? r < g.r : r > g.r);
	}
}q[N];
vector<int> b;

inline void add(int x)
{
	cnt[a[x]]++;
	fkcnt[get(a[x])]++;
}

inline void del(int x)
{
	cnt[a[x]]--;
	fkcnt[get(a[x])]--;
}

inline int query(int k)
{
	int place = get(k);
	int rp = getL(place + 1) - 1, res = 0;
	for (int i = k + 1; i <= rp; i++) res += cnt[i];
	for (int i = place + 1; i <= maxn; i++)
	{
		res += fkcnt[i];
	}
	return res;
}

int main()
{
	scanf("%d", &n);
	blo = sqrt(n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b.push_back(a[i]);
	scanf("%d", &m);
	for (int i = 1; i <= m; i++)
	{
		int l, r, k;
		scanf("%d%d%d", &l, &r, &k);
		b.push_back(k);
		q[i] = { i, l, r, k };
	}
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	for (int i = 1; i <= n; i++)
	{
		a[i] = upper_bound(b.begin(), b.end(), a[i]) - b.begin();
		maxn = max(maxn, get(a[i]));
	}
	for (int i = 1; i <= m; i++) q[i].k = upper_bound(b.begin(), b.end(), q[i].k) - b.begin();
	sort(q + 1, q + m + 1);
	int nl(1), nr(0);
	for (int i = 1; i <= m; i++)
	{
		int l = q[i].l, r = q[i].r;
		while (nr < r) add(++nr);
		while (nl > l) add(--nl);
		while (nl < l) del(nl++);
		while (nr > r) del(nr--);
		ans[q[i].id] = query(q[i].k);
	}
	for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
	return 0;
}