rt

P3834 【模板】可持久化线段树 2 过了，该题WA

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e5+5,M=5e3+5;
int n,m,Tree[N],tot,ans[M];
struct node{int opt,x,y,z;}q[N+M],lq[N+M],rq[N+M];
inline int read()
{
	char c=getchar();int now=0,nev=1;
	while(c<'0'||c>'9'){if(c=='-')nev=-1;c=getchar();}
	while(c>='0'&&c<='9')now=now*10-'0'+c,c=getchar();
	return now;
}inline void add(int x,int y){for(;x<=n;x+=x&-x)Tree[x]+=y;}
inline int query(int x){
	int y=0;
	for(;x;x-=x&-x)y+=Tree[x];
	return y;
}
inline void solve(int lval,int rval,int st,int ed)
{
	if(st>ed)return;
	if(lval==rval){
		for(int i=st;i<=ed;i++)ans[q[i].opt]=lval;
		return;
	}int mid=lval+rval>>1,lt=0,rt=0;
	for(int i=st;i<=ed;i++)
		if(q[i].opt==0){
			if(q[i].y<=mid)add(q[i].x,1),lq[++lt]=q[i];
			else rq[++rt]=q[i];
		}else{
			int tx=query(q[i].y)-query(q[i].x-1);
			if(tx>=q[i].z)lq[++lt]=q[i];
			else q[i].z-=tx,rq[++rt]=q[i];
		}
	for(int i=st;i<=ed;i++)if(q[i].opt==0&&q[i].y<=mid)add(q[i].x,-1);
	for(int i=1;i<=lt;i++)q[st+i-1]=lq[i];
	for(int i=1;i<=rt;i++)q[st+lt+i-1]=rq[i];
	solve(lval,mid,st,st+lt-1);
	solve(mid+1,rval,st+lt,ed);
	return;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)q[++tot].x=i,q[tot].y=read();
	for(int i=1;i<=m;i++)q[++tot].opt=i,q[tot].x=read(),q[tot].y=read(),q[tot].z=read();
	solve(-1e9,1e9,1,tot);
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}

感谢