这题真的有负数的数据吗。。。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
int a[1000005];
int trie[10000005][2],siz[10000005];
int cnt=1;
int root[1000005];
void insert(int id,int val){
	root[id]=++cnt;
	int u=root[id],v=root[id-1];
	for(int i=30; i>=0; i--){
		int k=(val&(1<<i))>>i;
		if(trie[v][k^1])
			trie[u][k^1]=trie[v][k^1];
		trie[u][k]=++cnt;
		siz[trie[u][k]]=siz[trie[v][k]]+1;
		u=trie[u][k];
		v=trie[v][k];
	}
	return;
}
int query(int lt,int rt,int val){
	int u=root[rt],v=root[lt-1];
	int ans=0;
	for(int i=30; i>=0; i--){
		if(siz[trie[u][0]]-siz[trie[v][0]]<val)
			val-=(siz[trie[u][0]]-siz[trie[v][0]]),ans+=(1<<i),u=trie[u][1],v=trie[v][1];
		else
			u=trie[u][0],v=trie[v][0];
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1; i<=n; i++)
		cin>>a[i],insert(i,a[i]);
	while(q--){
		int l,r,val;
		cin>>l>>r>>val;
		cout<<query(l,r,val)<<'\n';
	}
	return 0;
}

这是我的代码，用的是trie代替主席树，可以看到是没有处理负数的，但是过了

然后SPOJ上是过不掉的，刚因为这个卡了一会

如果是的话就当警示后人了