我在随机数据对拍的时候，发现有 RE 的情况。

因为莫队+平衡树中，莫队不断删除并不会重置 $cnt$，所以理论 $m$ 到顶的极品数据能够将值域较小的 Treap 卡掉。

是不是因为写法问题，栈重置不知道为什么竟然 T 了。请求证明或者调代码。

#include<bits/stdc++.h>
#define MAXN 100001
#define MAXM 50005
using namespace std;
struct node{
	int l,r,k,id,part;
}query[MAXM];
struct Node{
	int lson,rson,val,rnd,size;
}tree[MAXN];
int stk[MAXN];
int n,m,top,root,a[MAXN],ans[MAXN];
inline int newnode(int val){
	tree[stk[top]].val=val;
	tree[stk[top]].size=1;
	tree[stk[top]].rnd=rand();
	return stk[top--];
}
inline void push_up(int root){
	tree[root].size=tree[tree[root].lson].size+tree[tree[root].rson].size+1;
}
inline void split(int root,int val,int &x,int &y){
	if(root==0){
		x=y=0;
		return;
	}
	if(tree[root].val<=val){
		x=root;
		split(tree[root].rson,val,tree[root].rson,y);
	}else{
		y=root;
		split(tree[root].lson,val,x,tree[root].lson);
	}
	push_up(root);
}
inline int merge(int x,int y){
	if(!x||!y){
		return x+y;
	}
	if(tree[x].rnd<tree[y].rnd){
		tree[x].rson=merge(tree[x].rson,y);
		push_up(x);
		return x;
	}
	tree[y].lson=merge(x,tree[y].lson);
	push_up(y);
	return y;
}
inline void add(int val){
	int x,y;
	split(root,val,x,y);
	root=merge(merge(x,newnode(val)),y);
//	cout<<tree[root].size<<endl;
}
inline void del(int val){
	int x,y,z;
	split(root,val,x,z);
	split(x,val-1,x,y);
	stk[++top]=y;
	y=merge(tree[y].lson,tree[y].rson);
	root=merge(merge(x,y),z);
//	cout<<tree[root].size<<endl;
}
int get_val(int root,int rank){
	if(rank<=tree[tree[root].lson].size){
		return get_val(tree[root].lson,rank);
	}
	if(rank==tree[tree[root].lson].size+1){
		return root;
	}
	return get_val(tree[root].rson,rank-tree[tree[root].lson].size-1);
}
inline bool cmp(node x,node y){
	if(x.part!=y.part){
		return x.part<y.part;
	}
	return (x.part&1)?x.r<y.r:x.r>y.r;
}
int main(){
	srand(time(0));
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		stk[++top]=i;
	}
	int newn=sqrt(n);
	for(int i=1;i<=m;++i){
		scanf("%d %d %d",&query[i].l,&query[i].r,&query[i].k);
		query[i].id=i;
		query[i].part=query[i].l/newn;
	}
	sort(query+1,query+1+m,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;++i){
		while(l>query[i].l){
			add(a[--l]);
		}
		while(r<query[i].r){
			add(a[++r]);
		}
		while(l<query[i].l){
			del(a[l++]);
		}
		while(r>query[i].r){
			del(a[r--]);
		}
		ans[query[i].id]=tree[get_val(root,query[i].k)].val;
	}
	for(register int i=1;i<=m;++i){
		printf("%d\n",ans[i]);
	}
	return 0;
}