主席树开6e6不就能过吗..为啥我开了1e7还是RE...

QWQ

link

#include <bits/stdc++.h>
using namespace std;
const int Na = 3e5+10;
const int N = 6e6+10;
int n, m, len, tot;
int a[Na], lsh[Na], rt[Na], temp[2][Na], cnt[2];
struct Node{
	int ls, rs, v;
}f[N];
void update(int &k, int l, int r, int x)
{
	if(!k) k = ++tot;
	if(l==r){++f[k].v;return;}
	int mid = l+r>>1;
	if(mid>=x) update(f[k].ls, l, mid, x);
	else update(f[k].rs, mid+1, r, x);
	f[k].v = f[f[k].ls].v+f[f[k].rs].v;
}
void add(int x, int v)
{
	for(int i=x;i<=n;i+=i&-i) update(rt[i], 1, len, a[x]);
}
int query(int l, int r, int x)
{
	if(l==r) return l;
	int mid = l+r>>1, sum = 0;
	for(int i=1;i<=cnt[1];i++) sum += f[f[temp[1][i]].ls].v;
	for(int i=1;i<=cnt[0];i++) sum -= f[f[temp[0][i]].ls].v;
	if(sum>=x) 
	{
		for(int i=1;i<=cnt[1];i++) temp[1][i] = f[temp[1][i]].ls;
		for(int i=1;i<=cnt[0];i++) temp[0][i] = f[temp[0][i]].ls;
		return query(l, mid, x);
	}
	else 
	{
		for(int i=1;i<=cnt[1];i++) temp[1][i] = f[temp[1][i]].rs;
		for(int i=1;i<=cnt[0];i++) temp[0][i] = f[temp[0][i]].rs;
		return query(mid+1, r, x-sum);
	}
}
int get_num(int l, int r, int x)
{
	cnt[0] = cnt[1] = 0;
	for(int i=r;i;i-=i&-i) temp[1][++cnt[1]] = rt[i];
	for(int i=l-1;i;i-=i&-i) temp[0][++cnt[0]] = rt[i];
	return query(1, len, x);
}
int main()
{
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
		lsh[++len] = a[i];
	}
	sort(lsh+1, lsh+1+len);
	len = unique(lsh+1, lsh+1+len)-lsh-1;
	for(int i=1;i<=n;i++)
	{
		a[i] = lower_bound(lsh+1, lsh+len+1, a[i])-lsh;
		add(i, 1);
	}
	for(int i=1;i<=m;i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		cout << lsh[get_num(x, y, z)] << endl;
	}
	return 0;
}