入门题P3380 40pts WA

代码简短易懂，相信各位实力惊人得大佬都看得懂并 1ms 调完，谢谢了！！！

哎听 xft 说300行往上的代码没人调，我这次放个 400 行的是不是有人调了/qd/qd/qd

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline long long lev(long long x){
	if(x){
		return 32-__builtin_clz(x);
	}
	else{
		return 1;
	}
}
inline pair<int,int>lca(int u,int v){
	if(u==v){
		return make_pair(u,v);
	}
	int log_len=32-__builtin_clz(u^v);
	int len=1<<log_len;
	int l=(u>>log_len)<<log_len;
	return make_pair(l,l|(len-1));
}
namespace seg_y{
	long long log_interval_y,cnt;
	struct node_y{
		int ch[2],l,r,sum;
	}tree[12000005];
	inline long long new_node(){
		return ++cnt;
	}
	inline void init(int x){
		log_interval_y=x;
		cnt=0;
		return;
	}
	inline long long new_root(){
		int ret=new_node();
		tree[ret].l=0;
		tree[ret].r=(1<<log_interval_y)-1;
		tree[ret].sum=0;
		return ret;
	}
	inline void push_up(int u){
		tree[u].sum=tree[tree[u].ch[0]].sum+tree[tree[u].ch[1]].sum;
		return;
	}
	inline bool handle(int u,int son,int pos,int val){
		bool ret=1;
		if(tree[u].ch[son]==0){
			int v=new_node();
			tree[u].ch[son]=v;
			tree[v].sum=val;
			tree[v].l=pos;
			tree[v].r=pos;
			push_up(u);
		}
		else if(tree[tree[u].ch[son]].l==tree[tree[u].ch[son]].r){
			if(tree[tree[u].ch[son]].l==pos){
				tree[tree[u].ch[son]].sum=val;
				push_up(u);
			}
			else{
				pair<int,int>_lca=lca(pos,tree[tree[u].ch[son]].l);
				int f=new_node();
				tree[f].l=_lca.first;
				tree[f].r=_lca.second;
				int v=new_node();
				tree[v].sum=val;
				tree[v].l=pos;
				tree[v].r=pos;
				if(pos<tree[tree[u].ch[son]].l){
					tree[f].ch[0]=v;
				}
				else{
					tree[f].ch[0]=tree[u].ch[son];
				}
				tree[f].ch[1]=(v^tree[u].ch[son])^tree[f].ch[0];
				tree[u].ch[son]=f;
				push_up(f);
				push_up(u);
			}
		}
		else if(pos<tree[tree[u].ch[son]].l||pos>tree[tree[u].ch[son]].r){
			pair<int,int>_lca=lca(pos,tree[tree[u].ch[son]].l);
			int f=new_node();
			tree[f].l=_lca.first;
			tree[f].r=_lca.second;
			int v=new_node();
			tree[v].sum=val;
			tree[v].l=pos;
			tree[v].r=pos;
			if(pos<tree[tree[u].ch[son]].l){
				tree[f].ch[0]=v;
			}
			else{
				tree[f].ch[0]=tree[u].ch[son];
			}
			tree[f].ch[1]=(v^tree[u].ch[son])^tree[f].ch[0];
			tree[u].ch[son]=f;
			push_up(f);
			push_up(u);
		}
		else{
			ret=0;
		}
		return ret;
	}
	inline void _set(int u,int pos,int val){
		int mid=(tree[u].l+tree[u].r)/2;
		if(pos<=mid){
			bool ret=handle(u,0,pos,val);
			if(ret==0){
				_set(tree[u].ch[0],pos,val);
				push_up(u);
			}
		}
		else{
			bool ret=handle(u,1,pos,val);
			if(ret==0){
				_set(tree[u].ch[1],pos,val);
				push_up(u);
			}
		}
		return;
	}
	inline long long _query(int u,int l,int r){
		if(u==0){
			return 0;
		}
		int L=tree[u].l;
		int R=tree[u].r;
		if(L>r||R<l){
			return 0;
		}
		if(l<=L&&R<=r){
			return tree[u].sum;
		}
		return _query(tree[u].ch[0],l,r)+_query(tree[u].ch[1],l,r);
	}
	inline long long find_pos(int u,int pos){
		while(u){
			if(tree[u].r<pos||tree[u].l>pos){
				return 0;
			}
			if(tree[u].l==tree[u].r){
				break;
			}
			int mid=(tree[u].l+tree[u].r)/2;
			u=tree[u].ch[pos>mid];
		}
		return u;
	}
	inline long long clone(int u){
		int ret=new_node();
		tree[ret].l=tree[u].l;
		tree[ret].r=tree[u].r;
		tree[ret].sum=tree[u].sum;
		if(tree[u].ch[0]){
			tree[ret].ch[0]=clone(tree[u].ch[0]);
		}
		else{
			tree[ret].ch[0]=0;
		}
		if(tree[u].ch[1]){
			tree[ret].ch[1]=clone(tree[u].ch[1]);
		}
		else{
			tree[ret].ch[1]=0;
		}
		return ret;
	}
}
namespace seg_x{
	long long log_interval_x;
	struct node_x{
		int ch[2],l,r,rt;
	}tree[200005];
    int cnt,root;
	inline long long new_node(){
		return ++cnt;
	}
	inline void init(int x){
		log_interval_x=x;
		cnt=0;
		root=new_node();
		tree[root].l=0;
		tree[root].r=(1<<log_interval_x)-1;
		tree[root].rt=seg_y::new_root();
	}
	inline void push_up(int u,int y){
		int lcpos=seg_y::find_pos(tree[tree[u].ch[0]].rt,y);
		int rcpos=seg_y::find_pos(tree[tree[u].ch[1]].rt,y);
		int res=seg_y::tree[lcpos].sum+seg_y::tree[rcpos].sum;
		seg_y::_set(tree[u].rt,y,res);
		return;
	}
	inline bool handle(int u,int son,int x,int y,int val){
		bool ret=1;
    	if(tree[u].ch[son]==0){
    		int v=new_node();
    		tree[u].ch[son]=v;
    		tree[v].l=x;
    		tree[v].r=x;
    		tree[v].rt=seg_y::new_root();
    		seg_y::_set(tree[v].rt,y,val);
    		push_up(u,y);
		}
		else if(tree[tree[u].ch[son]].l==tree[tree[u].ch[son]].r){
			if(tree[tree[u].ch[son]].l==x){
				seg_y::_set(tree[tree[u].ch[son]].rt,y,val);
				push_up(u,y);
			}
			else{
				pair<int,int>_lca=lca(x,tree[tree[u].ch[son]].l);
				int f=new_node();
				tree[f].l=_lca.first;
				tree[f].r=_lca.second;
				tree[f].rt=seg_y::clone(tree[tree[u].ch[son]].rt);
				int v=new_node();
				tree[v].l=x;
				tree[v].r=x;
				tree[v].rt=seg_y::new_root();
				seg_y::_set(tree[v].rt,y,val);
				if(x<tree[tree[u].ch[son]].l){
					tree[f].ch[0]=v;
				}
				else{
					tree[f].ch[0]=tree[u].ch[son];
				}
				tree[f].ch[1]=(v^tree[u].ch[son])^tree[f].ch[0];
				tree[u].ch[son]=f;
				push_up(f,y);
				push_up(u,y);
			}
		}
		else if(x<tree[tree[u].ch[son]].l||x>tree[tree[u].ch[son]].r){
			pair<int,int>_lca=lca(x,tree[tree[u].ch[son]].l);
			int f=new_node();
			tree[f].l=_lca.first;
			tree[f].r=_lca.second;
			tree[f].rt=seg_y::clone(tree[tree[u].ch[son]].rt);
			int v=new_node();
			tree[v].l=x;
			tree[v].r=x;;
			tree[v].rt=seg_y::new_root();
			seg_y::_set(tree[v].rt,y,val);
			if(x<tree[tree[u].ch[son]].l){
				tree[f].ch[0]=v;
			}
			else{
				tree[f].ch[0]=tree[u].ch[son];
			}
			tree[f].ch[1]=(v^tree[u].ch[son])^tree[f].ch[0];
			tree[u].ch[son]=f;
			push_up(f,y);
			push_up(u,y);
		}
		else{
			ret=0;
		}
		return ret;
	}
	inline void _set(int u,int x,int y,int val){
		int mid=(tree[u].l+tree[u].r)/2;
		if(x<=mid){
			bool ret=handle(u,0,x,y,val);
			if(ret==0){
				_set(tree[u].ch[0],x,y,val);
				push_up(u,y);
			}
		}
		else{
			bool ret=handle(u,1,x,y,val);
			if(ret==0){
				_set(tree[u].ch[1],x,y,val);
				push_up(u,y);
			}
		}
		return;
	}
	inline void set(int x,int y,int val){
		_set(root,x,y,val);
		return;
	}
    inline long long _query(int u,int xl,int xr,int yl,int yr){
    	if(u==0){
    		return 0;
		}
		int L=tree[u].l;
		int R=tree[u].r;
		if(L>xr||R<xl){
			return 0;
		}
		if(xl<=L&&R<=xr){
			return seg_y::_query(tree[u].rt,yl,yr);
		}
		return _query(tree[u].ch[0],xl,xr,yl,yr)+_query(tree[u].ch[1],xl,xr,yl,yr);
	}
    inline long long query(int xl,int xr,int yl,int yr){
    	return _query(root,xl,xr,yl,yr);
	}
    inline long long find_kth(int rk,int yl,int yr){
    	int u=root;
    	if(tree[u].ch[0]==0||tree[u].ch[1]==0){
    		u=tree[u].ch[!tree[u].ch[0]];
		}
		while(tree[u].ch[0]&&tree[u].ch[1]){
			int lcsum=seg_y::_query(tree[tree[u].ch[0]].rt,yl,yr);
			if(lcsum>=rk){
				u=tree[u].ch[0];
			}
			else{
				rk-=lcsum;
				u=tree[u].ch[1];
			}
		}
		return tree[u].l;
	}
}
int n,m,op;
int l,r,pos,k;
int a[100005];
inline void init(int x,int y){
	seg_y::init(lev(y));
	seg_x::init(lev(x));
	return;
}
inline void add(int x,int y,int val){
	seg_x::set(x,y,val+seg_x::query(x,x,y,y));
}
inline void arr_set(int pos,int val){
	a[pos]=val;
	add(val,pos,1);
	return;
}
inline void update(int pos,int val){
	add(a[pos],pos,-1);
	add(val,pos,1);
	a[pos]=val;
	return;
}
inline long long get_rk(long long l,long long r,long long k){
	return seg_x::query(0,k-1,l,r)+1;
}
inline long long find_kth(long long l,long long r,long long k){
	return seg_x::find_kth(k,l,r);
}
inline long long min_element(long long l,long long r){
	return find_kth(l,r,1);
}
inline long long max_element(long long l,long long r){
	return find_kth(l,r,r-l+1);
}
inline long long prec(long long l,long long r,long long k){
	if(k<=min_element(l,r)){
		return -INT_MAX;
	}
	else{
		return find_kth(l,r,get_rk(l,r,k)-1);
	}
}
inline long long succ(long long l,long long r,long long k){
	if(k>=max_element(l,r)){
		return INT_MAX;
	}
	else{
		return find_kth(l,r,get_rk(l,r,k+1));
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	init(1000000000,n);
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		arr_set(i,x);
	}
	while(m--){
		cin>>op;
		if(op==1){
			cin>>l>>r>>k;
			cout<<get_rk(l,r,k)<<'\n';
		}
		else if(op==2){
			cin>>l>>r>>k;
			cout<<find_kth(l,r,k)<<'\n';
		}
		else if(op==3){
			cin>>pos>>k;
			update(pos,k);
		}
		else if(op==4){
			cin>>l>>r>>k;
			cout<<prec(l,k,r)<<'\n';
		}
		else{
			cin>>l>>r>>k;
			cout<<succ(l,r,k)<<'\n';
		}
	}
}