这是可持久化线段树模板题，粘贴模板即可。

#include <bits/stdc++.h>
using namespace std;
namespace INPUT_SPACE
{
	const int S = 1 << 25;
	char B[S];
	char* H;
	char* T;
	inline char gc()
	{
		if (H == T)
		{
			H = B;
			T = B + fread(B, 1, S, stdin);
		}
		if (H == T) return 0;
		char* I = H;
		H++;
		return *I;
	}
	inline unsigned int inn()
	{
		unsigned int x = 0;
		char c;
		c = gc();
		while (c < '0') c = gc();
		while (c >= '0')
		{
			x *= 10;
			x += c - '0';
			c = gc();
		}
		return x;
	}
};
using INPUT_SPACE::inn;
const int PTD = 30;
struct V
{
	int a;
	int ll;
	int rr;
	int l;
	int r;
};
struct U
{
	V v[8000012];
	int roots[200012];
	int ts;
	int st;
	void init(int n)
	{
		ts = n;
		st = n;
		for (int i = 1; i <= n; i++)
			v[i].rr = (1 << PTD) - 1;
		for (int i = 1; i <= n; i++)
			roots[i] = i;
	}
	void expand(int b)
	{
		if (v[b].ll == v[b].rr) return;
		if (v[b].l == 0)
		{
			ts++;
			v[ts] = (V){0, v[b].ll, (v[b].ll + v[b].rr) >> 1, 0, 0};
			v[b].l = ts;
		}
		if (v[b].r == 0)
		{
			ts++;
			v[ts] = (V){0, ((v[b].ll + v[b].rr) >> 1) + 1, v[b].rr, 0, 0};
			v[b].r = ts;
		}
	}
	bool create(int x, int b)
	{
		if (v[b].ll == x && v[b].rr == x) return true;
		expand(b);
		int lmid = (v[b].ll + v[b].rr) >> 1, rmid = lmid + 1;
		if (x <= lmid) return create(x, v[b].l);
		if (x >= rmid) return create(x, v[b].r);
	}
	bool add(int x, int y, int b, int c)
	{
		v[b].a += v[c].a + y;
		if (v[b].ll == x && v[b].rr == x) return true;
		int lmid = (v[b].ll + v[b].rr) >> 1, rmid = lmid + 1;
		if (x <= lmid) v[b].r = v[c].r;
		if (x >= rmid) v[b].l = v[c].l;
		expand(b);
		if (x <= lmid) return add(x, y, v[b].l, v[c].l);
		if (x >= rmid) return add(x, y, v[b].r, v[c].r);
	}
	int get(int l, int r, int b)
	{
		if (!b) return 0;
		if (l == v[b].ll && r == v[b].rr) return v[b].a;
		int lmid = (v[b].ll + v[b].rr) >> 1, rmid = lmid + 1;
		if (r <= lmid) return get(l, r, v[b].l);
		if (l >= rmid) return get(l, r, v[b].r);
		return get(l, lmid, v[b].l) + get(rmid, r, v[b].r);
	}
};
U t;
int a[200012];
int main()
{
	int n = inn(), m = inn();
	t.init(n + 1);
	for (int i = 1; i <= n; i++)
	{
		a[i] = inn();
		t.create(a[i], t.roots[n + 1]);
	}
	t.roots[0] = t.roots[n + 1];
	for (int i = 1; i <= n; i++)
		t.add(a[i], 1, t.roots[i], t.roots[i - 1]);
	for (int i = 1; i <= m; i++)
	{
		int l = inn(), r = inn(), k = inn();
		int ll = 0, rr = 1073741823;
		while (ll < rr)
		{
			int mid = (0ll + ll + rr) / 2;
			int x = t.get(0, mid, t.roots[r]);
			int y = t.get(0, mid, t.roots[l - 1]);
			if (x - y >= k) rr = mid;
			else ll = mid + 1;
		}
		int a1 = t.get(0, ll, t.roots[r]) - t.get(0, ll, t.roots[l - 1]);
		int a2 = t.get(0, ll - 1, t.roots[r]) - t.get(0, ll - 1, t.roots[l - 1]);
		cout << a1 - a2 << endl;
	}
	return 0;
}