P3834求助

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	int x = 0,p = 1;
	char c = getchar();
	while(c > '9' || c < '0')	p = c == '-' ? -1 : 1,c = getchar();
	while(c >= '0' && c <= '9')	x = (x << 1) + (x << 3) + (c ^ 48),c = getchar();
	return p * x;
}
template<typename _Tp> inline void _write(_Tp x) { if(x > 9) _write(x / 10); putchar(x % 10 | 48); }
template<typename _Tp> inline void write(_Tp x) { if(x < 0) putchar('-'),x = -x; _write(x); }
template<typename _Tp> inline void writeln(_Tp x) { write(x); puts(""); }
const int N = 2e5 + 10;
int n,m,Q,a[N],arr[N],L,b[N],ans[N];
struct BIT
{
	int bit[N];
	inline void add(int x,int k) { for(;x <= m;x += (x & -x)) bit[x] += k; }
	inline int query(int x) { int ans = 0; for(;x;x -= (x & -x)) ans += bit[x]; return ans; }
} tr;
map<int,int> rk;
struct Query { int l,r,k,id; } q[N];
inline bool cmp(Query x,Query y)
{
	if(b[x.l] != b[y.l])	return b[x.l] < b[y.l];
	if(b[x.l] & 1)	return x.r < y.r;
	return x.r > y.r;
}
inline void add(int x) { tr.add(a[x],1); }
inline void del(int x) { tr.add(a[x],-1); }
signed main()
{
	n = read(); Q = read(); L = (sqrt(n) + (sqrt(n * log2(n)))) / 2;
	for(int i = 1;i <= n;i++)	a[i] = arr[i] = read();
	for(int i = 1;i <= n;i++)	b[i] = (i - 1) / L + 1;
	sort(arr + 1,arr + n + 1);
	m = unique(arr + 1,arr + n + 1) - arr - 1;
	for(int i = 1;i <= m;i++)	rk[arr[i]] = i;
	for(int i = 1;i <= n;i++)	a[i] = rk[a[i]];
	for(int i = 1;i <= Q;i++)	q[i].l = read(),q[i].r = read(),q[i].k = read(),q[i].id = i;
	sort(q + 1,q + Q + 1,cmp);
	int l = 1,r = 0;
	for(int i = 1;i <= Q;i++)
	{
		while(l < q[i].l)	del(l++);
		while(l > q[i].l)	add(--l);
		while(r > q[i].r)	del(r--);
		while(r < q[i].r)	add(++r);
		int L = 1,R = m,mid;
		while(L < R)
		{
			mid = L + R >> 1;
			if(tr.query(mid) < q[i].k)	L = mid + 1;
			else	R = mid;
//			printf("%lld,%lld,%lld\n",i,L,R);
		}
		ans[q[i].id] = arr[L];
	}
	for(int i = 1;i <= Q;i++)	writeln(ans[i]);
	return 0;
}