WA on 1,3,4,5,7 求条

#include<bits/stdc++.h>
#define int long long
#define endl putchar('\n')
#define psp putchar(' ')
#define lc f[p].l
#define rc f[p].r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N=5e4+5;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=getchar();
	return x*f;
}
void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x<10){putchar(x+'0');return;}
	print(x/10);
	putchar(x%10+'0');
}
void putstr(string s){
	for(int i=0;i<s.size();i++)putchar(s[i]);
}
int lowbit(int x){
	return x&-x;
}
int n,m,k;
int T;
struct node{
	int l,r,ans;
}f[(int)4e7];
int bit[N];
int cnt;
int rt[N];
int idx;
int a[N];
int create(int p){
	f[++idx]=f[p];
	return idx;
}
void update(int &p,int L,int R,int x,int k){
	p=create(p);
	if(L==R){
		f[p].ans+=k;
		return;
	}
	int mid=L+R>>1;
	if(x<=mid)update(lc,L,mid,x,k);
	else update(rc,mid+1,R,x,k);
	f[p].ans=f[lc].ans+f[rc].ans;
}
void add(int x,int val,int num){
	while(x<=n){
		update(rt[x],1,cnt,val,num);
		x+=lowbit(x);
	}
}
int ls[N];
int rs[N];
int cntl,cntr;
int query_num(int L,int R,int k){
	if(L==R)return L;
	int mid=L+R>>1;
	int res=0;
	for(int i=1;i<=cntr;i++)res+=f[f[rs[i]].l].ans;
	for(int i=1;i<=cntl;i++)res-=f[f[ls[i]].l].ans;
	if(k<=res){
		for(int i=1;i<=cntr;i++)rs[i]=f[rs[i]].l;
		for(int i=1;i<=cntl;i++)ls[i]=f[ls[i]].l;
		return query_num(L,mid,k);
	}
	else{
		for(int i=1;i<=cntr;i++)rs[i]=f[rs[i]].r;
		for(int i=1;i<=cntl;i++)ls[i]=f[ls[i]].r;
		return query_num(mid+1,R,k-res);
	}
}
int query_rank(int L,int R,int x){
	if(L==R)return 0;
	int mid=L+R>>1;
	if(x<=mid){
		for(int i=1;i<=cntr;i++)rs[i]=f[rs[i]].l;
		for(int i=1;i<=cntl;i++)ls[i]=f[ls[i]].l;
		return query_rank(L,mid,x);
	}
	else{
		int res=0;
		for(int i=1;i<=cntr;i++)res+=f[f[rs[i]].l].ans;
		for(int i=1;i<=cntl;i++)res-=f[f[ls[i]].l].ans;
		for(int i=1;i<=cntr;i++)rs[i]=f[rs[i]].r;
		for(int i=1;i<=cntl;i++)ls[i]=f[ls[i]].r;
		return query_rank(mid+1,R,x)+res;
	}
}
void point(int l,int r){
	cntl=cntr=0;
	while(r){
		rs[++cntr]=rt[r];
		r-=lowbit(r);
	}
	while(l){
		ls[++cntl]=rt[l];
		l-=lowbit(l);
	}
}
struct que{
	int op,l,r,x;
}q[N];
int num[N*4];
int M;
int deepseek(int x){
	int l=1,r=cnt;
	while(l<r){
		int mid=l+r>>1;
		if(num[mid]>=x)r=mid;
		else l=mid+1;
	}
	return r;
}
signed main(){
//	freopen("P3380_1.in","r",stdin);
//	freopen("qwq.txt","w",stdout);
	//ios::sync_with_stdio(0);
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read(),num[++M]=a[i];
	for(int i=1;i<=m;i++){
		q[i].op=read(),q[i].l=read(),q[i].r=read();
		if(q[i].op!=3)q[i].x=read();
		if(q[i].op==1){
			num[++M]=q[i].x;
		}
		else if(q[i].op==3){
			num[++M]=q[i].r;
		}
		else if(q[i].op==4){
			num[++M]=q[i].x;
		}
		else if(q[i].op==5){
			num[++M]=q[i].x+1;
		}
	}
	sort(num+1,num+1+M);
	for(int i=1;i<=M;i++){
		if(num[i]!=num[i-1])num[++cnt]=num[i];
	}
	for(int i=1;i<=n;i++)a[i]=deepseek(a[i]);
	for(int i=1;i<=n;i++)add(i,a[i],1);
	for(int i=1;i<=m;i++){
		if(q[i].op==1){
			q[i].x=deepseek(q[i].x);
		}
		else if(q[i].op==2){
			//啥都没有
		}
		else if(q[i].op==3){
			q[i].r=deepseek(q[i].r);
		}
		else if(q[i].op==4){
			q[i].x=deepseek(q[i].x);
		}
		else{
			q[i].x=deepseek(q[i].x);
		}
	}
	for(int i=1;i<=m;i++){
		if(q[i].op==1){
			point(q[i].l-1,q[i].r);
			print(query_rank(1,cnt,q[i].x)+1),endl;
		}
		else if(q[i].op==2){
			point(q[i].l-1,q[i].r);
			print(num[query_num(1,cnt,q[i].x)]),endl;
		}
		else if(q[i].op==3){
			add(q[i].l,a[q[i].l],-1);
			a[q[i].l]=q[i].r;
			add(q[i].l,a[q[i].l],1);
		}
		else if(q[i].op==4){
			point(q[i].l-1,q[i].r);
			int rk=query_rank(1,cnt,q[i].x)+1;
			point(q[i].l-1,q[i].r);
			if(rk>1)print(num[query_num(1,cnt,rk-1)]),endl;
			else putstr("-2147483647\n");
		}
		else{
			point(q[i].l-1,q[i].r);
			int rk=query_rank(1,cnt,q[i].x)+1;
			point(q[i].l-1,q[i].r); 
			if(rk>=q[i].r-q[i].l+2)putstr("2147483647\n");
			else print(num[query_num(1,cnt,rk)]),endl;
		}
	}
}