又 快 又 错

Code:

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

const int R = 2e5 + 10;
struct Node
{
	int l, r, val, size;
	long long key;
} tree[R];
int tot, root;
mt19937 rd;
int crt(int val)
{
	tree[++tot].val = val;
	tree[tot].size = 1;
	tree[tot].key = rd();
	return tot;
}
void pushup(int k)
{
	tree[k].size = tree[tree[k].l].size + tree[tree[k].r].size + 1;
}
void split(int k, int sz, int &x, int &y) // 按大小分裂
{
	if (k == 0)
	{
		x = y = 0;
		return;
	}
	if (tree[tree[k].l].size + 1 <= sz)
	{
		x = k;
		split(tree[k].r, sz - (tree[tree[k].l].size + 1), tree[k].r, y);
	}
	else
	{
		y = k;
		split(tree[k].l, sz, x, tree[k].l);
	}
	pushup(k);
}
int merge(int x, int y)
{
	if (x == 0 || y == 0)
		return x + y;
	if (tree[x].key > tree[y].key)
	{
		tree[x].r = merge(tree[x].r, y);
		pushup(x);
		return x;
	}
	else
	{
		tree[y].l = merge(x, tree[y].l);
		pushup(y);
		return y;
	}
}
int kth(int x, int k)
{
	while (x)
	{
		if (tree[tree[x].l].size + 1 == k)
			break;
		if (tree[tree[x].l].size >= k)
			x = tree[x].l;
		else
		{
			k = k - (tree[tree[x].l].size + 1);
			x = tree[x].r;
		}
	}
	return tree[x].val;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m, l, r, k, x, y, z;
	cin >> n >> m;
	int j;
	for (j = 1; j <= n; ++j)
	{
		cin >> x;
		root = merge(root, crt(x));
	}
	for (j = 1; j <= m; ++j)
	{
		cin >> l >> r >> k;
		split(root, l - 1, x, y);
		// cout << y << ' ';
		split(y, r - l + 1, y, z);
		// cout << y << ' ';
		cout << kth(y, k) << '\n';
		// root = merge(merge(x, y), z);
		root = merge(merge(x, y), z);
	}
	// for (j = 1; j <= n; ++j)
	// 	cout << tree[j].l << ' ' << tree[j].r << ' ' << tree[j].key << '\n';
	return 0;
}