题解

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define db double
#define il inline
using namespace std;
void read(int &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
void read(ll &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
const int N=5e4+5,M=1e8;
int rt[M*4],ls[N*20*20],rs[N*20*20],tree[N*20*20],tot,root;
int n,m,a[N];
void push_up(int x){
	tree[x]=tree[ls[x]]+tree[rs[x]];
}
void update(int x,int l,int r,int pos,int w){
	if(l==r){
		tree[x]+=w;return;
	}
	int mid=(l+r)/2;
	if(pos<=mid){
		if(!ls[x])ls[x]=++tot;update(ls[x],l,mid,pos,w);
	}else{
		if(!rs[x])rs[x]=++tot;update(rs[x],mid+1,r,pos,w);
	}
	push_up(x);
}
int query(int x,int l,int r,int ql,int qr){
	if(!x)return 0;if(ql<=l&&qr>=r)return tree[x];
	int mid=(l+r)/2,re=0;
	if(ql<=mid){
		if(ls[x])re+=query(ls[x],l,mid,ql,qr);
	}
	if(qr>mid){
		if(rs[x])re+=query(rs[x],mid+1,r,ql,qr);
	}
	return re;
}
void upd(int x,int l,int r,int p,int p2,int w){
//	cout<<x<<' '<<l<<' '<<r<<endl;
	if(rt[x]==0)rt[x]=++tot;
//	cout<<rt[x]<<' '<<l<<' '<<r<<' '<<p2<<' '<<w<<"add"<<endl;
	update(rt[x],1,n,p2,w);
//	cout<<query(rt[x],1,n,p2,p2)<<endl;
	if(l==r)return;
	int mid=(l+r)/2;
	if(p<=mid){
		if(!ls[x]){
//			cout<<"LS"<<x<<endl;
			ls[x]=++tot;
		}
		upd(ls[x],l,mid,p,p2,w);
	}else{
		if(!rs[x])rs[x]=++tot;upd(rs[x],mid+1,r,p,p2,w);
	}
}
int ran(int x,int l,int r,int ql,int qr,int wl,int wr){//在第一个线段树内 
	if(ql<=l&&qr>=r){
		return query(rt[x],1,n,wl,wr);
	} 
	int re=0,mid=(l+r)/2;
	if(ql<=mid&&ls[x]){
		re+=ran(ls[x],l,mid,ql,qr,wl,wr);
	}
	if(qr>mid&&rs[x]){
		re+=ran(rs[x],mid+1,r,ql,qr,wl,wr);
	}
	return re;
}
int kth(int x,int l,int r,int w,int ql,int qr){
	if(l==r)return l;int mid=(l+r)/2,tmp=query(rt[ls[x]],1,n,ql,qr);
//	cout<<x<<' '<<l<<' '<<r<<' '<<w<<' '<<tmp<<' '<<' '<<rt[ls[x]]<<endl;
	if(tmp>=w)return kth(ls[x],l,mid,w,ql,qr);else return kth(rs[x],mid+1,r,w-tmp,ql,qr);
}
int pre(int l,int r,int x){
	if(ran(root,1,M,1,x-1,l,r)==ran(root,1,M,0,0,l,r))return -2147483647;
	else return kth(root,1,M,ran(root,1,M,0,x-1,l,r),l,r); 
}
int nex(int l,int r,int x){
	if(ran(root,1,M,0,x,l,r)==ran(root,1,M,0,M,l,r))return 2147483647;
	return kth(root,1,M,ran(root,1,M,0,x,l,r)+1,l,r);
}
int main(){
	read(n);read(m);
	root=++tot;
	for(int i=1;i<=n;i++){
		read(a[i]);upd(root,1,M,a[i],i,1);
	}
//	cout<<1234566;
	while(m--){
		int op;int l,r,x;read(op);read(l);read(r);if(op!=3)read(x);
		if(op==1)printf("%d\n",ran(root,1,M,0,x-1,l,r)+1);
		else if(op==2)printf("%d\n",kth(root,1,M,x,l,r));
		else if(op==3){
			upd(root,1,M,a[l],l,-1);a[l]=r;upd(root,1,M,a[l],l,1);
		} else if(op==4)printf("%d\n",pre(l,r,x));
		else printf("%d\n",nex(l,r,x));
	}
	
	return 0;
}