RT

错误信息“ read -, expected 9. ”

线段树套平衡树，平衡树使用AVL树

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
int read(){
	int w=0;
	bool s=0;
	char c=getchar();
	while(!isdigit(c)){
		s=(c=='-');
		c=getchar();
	}
	while(isdigit(c)){
		w=w*10+c-'0';
		c=getchar();
	}
	return s?-w:w;
}
const int N=300005,inf=2147483647;
int n,m,rg;
int a[N];
int max(int x,int y){
	if(x>y){
		return x;
	}
	return y;
}
int min(int x,int y){
	if(x<y){
		return x;
	}
	return y;
}
struct AVL_Tree{
	int cnt;
	struct Node{
		int val;
		int ls,rs;
		int hei,siz,cpy;
	};
	Node tr[N<<4];
	int root[N<<2];
	int sta[N<<4],top;
	AVL_Tree(){
		memset(root,0,sizeof(root));
		tr[0]=(Node){0,0,0,0,0,0};
		cnt=0,top=0;
	}
	void del(int x){
		sta[++top]=x;
	}
	int add(int v){
		int x;
		if(top){
			x=sta[top--];
		}
		else{
			x=++cnt;
		}
		tr[x]=(Node){v,0,0,1,1,1};
		return x;
	}
	void pushup(int x){
		tr[x].hei=max(tr[tr[x].ls].hei,tr[tr[x].rs].hei)+1;
		tr[x].siz=tr[tr[x].ls].siz+tr[tr[x].rs].siz+tr[x].cpy;
	}
	int  left_rotate(int x){
		int z=tr[x].rs;
		tr[x].rs=tr[z].ls;
		tr[z].ls=x;
		pushup(x);
		pushup(z);
		return z;
	}
	int right_rotate(int x){
		int y=tr[x].ls;
		tr[x].ls=tr[y].rs;
		tr[y].rs=x;
		pushup(x);
		pushup(y);
		return y;
	}
	int balance(int x){
		if(tr[tr[x].ls].hei==tr[tr[x].rs].hei+2){
			if(tr[tr[tr[x].ls].ls].hei>=tr[tr[tr[x].ls].rs].hei){
				x=right_rotate(x);
			}
			else{
				tr[x].ls=left_rotate(tr[x].ls);
				x=right_rotate(x);
			}
		}
		else if(tr[tr[x].ls].hei+2==tr[tr[x].rs].hei){
			if(tr[tr[tr[x].rs].rs].hei>=tr[tr[tr[x].rs].ls].hei){
				x=left_rotate(x);
			}
			else{
				tr[x].rs=right_rotate(tr[x].rs);
				x=left_rotate(x);
			}
		}
		return x;
	}
	int Imin(int x){
		if(!x){
			return x;
		}
		while(tr[x].ls){
			x=tr[x].ls;
		}
		return x;
	}
	int Imax(int x){
		if(!x){
			return x;
		}
		while(tr[x].rs){
			x=tr[x].rs;
		}
		return x;
	}
	int Iinsert(int x,int v){
		if(!x){
			x=add(v);
			return x;
		}
		if(tr[x].val==v){
			tr[x].cpy++;
		}
		else if(v<tr[x].val){
			tr[x].ls=Iinsert(tr[x].ls,v);
		}
		else{
			tr[x].rs=Iinsert(tr[x].rs,v);
		}
		pushup(x);
		return balance(x);
	}
	int Iremove(int x,int v){
		if(!x){
			return x;
		}
		int y;
		if(v<tr[x].val){
			tr[x].ls=Iremove(tr[x].ls,v);
		}
		else if(v>tr[x].val){
			tr[x].rs=Iremove(tr[x].rs,v);
		}
		else if(tr[x].cpy>1){
			tr[x].cpy--;
		}
		else if(tr[x].ls&&tr[x].rs){
			y=Imin(tr[x].rs);
			tr[x].val=tr[y].val;
			tr[x].cpy=tr[y].cpy;
			tr[y].cpy=1;
			tr[x].rs=Iremove(tr[x].rs,tr[x].val);
		}
		else if(tr[x].ls||tr[x].rs){
			x=tr[x].ls^tr[x].rs;
		}
		else{
			del(x);
			x=0;
			return x;
		}
		pushup(x);
		return balance(x);
	}
	int Ifind(int x,int v){
		while(x&&tr[x].val!=v){
			if(v<tr[x].val){
				x=tr[x].ls;
			}
			else{
				x=tr[x].rs;
			}
		}
		return x;
	}
	int rank(int x,int v){
		int s=0;
		while(x){
			if(v<tr[x].val){
				x=tr[x].ls;
			}
			else if(v>tr[x].val){
				s+=tr[tr[x].ls].siz+tr[x].cpy;
				x=tr[x].rs;
			}
			else{
				return s+tr[tr[x].ls].siz;
			}
		}
		return s;
	}
	int Iselect(int x,int s){
		if(s<=tr[tr[x].ls].siz){
			return Iselect(tr[x].ls,s);
		}
		if(s>tr[tr[x].ls].siz+tr[x].cpy){
			return Iselect(tr[x].rs,s-(tr[tr[x].ls].siz+tr[x].cpy));
		}
		return x;
	}
	int Ipred(int x,int v){
		int res=0;
		while(x){
			if(tr[x].val<v){
				if(!res||tr[res].val<tr[x].val){
					res=x;
				}
				x=tr[x].rs;
			}
			else{
				x=tr[x].ls;
			}
		}
		return res;
	}
	int Isucc(int x,int v){
		int res=0;
		while(x){
			if(v<tr[x].val){
				if(!res||tr[x].val<tr[res].val){
					res=x;
				}
				x=tr[x].ls;
			}
			else{
				x=tr[x].rs;
			}
		}
		return res;
	}
	void insert(int rt,int v){
		root[rt]=Iinsert(root[rt],v);
	}
	void remove(int rt,int v){
		root[rt]=Iremove(root[rt],v);
	}
	int pred(int rt,int v){
		int x=Ipred(root[rt],v);
		if(!x){
			return -inf;
		}
		return tr[x].val;
	}
	int succ(int rt,int v){
		int x=Isucc(root[rt],v);
		if(!x){
			return inf;
		}
		return tr[x].val;
	}
	void print(int x){
		if(tr[x].ls){
			print(tr[x].ls);
		}
		for(int i=1;i<=tr[x].cpy;i++){
			printf("%d ",tr[x].val);
		}
		if(tr[x].rs){
			print(tr[x].rs);
		}
	}
};
AVL_Tree T;
struct Segment_Tree{
	#define mid ((le+ri)>>1)
	#define ls rt<<1
	#define rs rt<<1|1
	#define lson le,mid,ls
	#define rson mid+1,ri,rs
	void build(int le,int ri,int rt){
		for(int i=le;i<=ri;i++){
			T.insert(rt,a[i]);
		}
		if(le==ri){
			return;
		}
		build(lson);
		build(rson);
	}
	void modify(int le,int ri,int rt,int x,int y){
		T.remove(rt,a[x]);
		T.insert(rt,y);
		if(le==ri){
			return;
		}
		if(x<=mid){
			modify(lson,x,y);
		}
		else{
			modify(rson,x,y);
		}
	}
	int query_rank(int le,int ri,int rt,int x,int y,int z){
		if(x<=le&&ri<=y){
			return T.rank(T.root[rt],z);
		}
		int res=0;
		if(x<=mid){
			res+=query_rank(lson,x,y,z);
		}
		if(y>mid){
			res+=query_rank(rson,x,y,z);
		}
		return res;
	}
	int query_select(int x,int y,int z){
		int l=0,r=rg,res=0;
		while(l<=r){
			int m=(l+r)>>1;
			if(query_rank(1,n,1,x,y,m)+1>z){
				res=m;
				r=m-1;
			}
			else{
				l=m+1;
			}
		}
		return res-1;
	}
	int query_pred(int le,int ri,int rt,int x,int y,int z){
		if(x<=le&&ri<=y){
			return T.pred(rt,z);
		}
		int res=-inf;
		if(x<=mid){
			res=max(res,query_pred(lson,x,y,z));
		}
		if(y>mid){
			res=max(res,query_pred(rson,x,y,z));
		}
		return res;
	}
	int query_succ(int le,int ri,int rt,int x,int y,int z){
		if(x<=le&&ri<=y){
			return T.succ(rt,z);
		}
		int res=inf;
		if(x<=mid){
			res=min(res,query_succ(lson,x,y,z));
		}
		if(y>mid){
			res=min(res,query_succ(rson,x,y,z));
		}
		return res;
	}
};
Segment_Tree ST;
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		rg=max(rg,a[i]);
	}
	ST.build(1,n,1);
	int opt,x,y,z;
	for(int i=1;i<=m;i++){
		opt=read(),x=read(),y=read();
		if(opt==1){
			z=read();
			printf("%d\n",ST.query_rank(1,n,1,x,y,z)+1);
		}
		if(opt==2){
			z=read();
			printf("%d\n",ST.query_select(x,y,z));
		}
		if(opt==3){
			ST.modify(1,n,1,x,y);
			a[x]=y;
			rg=max(rg,y);
		}
		if(opt==4){
			z=read();
			printf("%d\n",ST.query_pred(1,n,1,x,y,z));
		}
		if(opt==5){
			z=read();
			printf("%d\n",ST.query_succ(1,n,1,x,y,z));
		}
	}
	return 0;
}