AC #2,#9

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000000;
struct Node{
	int ls,rs,cnt;
}t[maxn*21];
int root[maxn],tot,n,m,a[maxn],b[maxn],tot2=0,stot=0;//tot2:离散化
int clone(int p){//旧点
	t[++tot]=t[p];
	return tot;
}
int getrank(int x){return lower_bound(b+1,b+tot2+1,x)-b;}//映射
int getnum(int x){return b[x];}
void build(int &id,int l,int r){//加&更新新版本节点编号
	if(l==r)return;
	int mid=(l+r)>>1;
	build(t[id].ls,l,mid);
	build(t[id].rs,mid+1,r);
}//没有动态开点
void up(int id){t[id].cnt=t[t[id].ls].cnt+t[t[id].rs].cnt;}
void update(int &id,int l,int r,int x,int val){//x:修改的对应值（因为是维护的是值域）
	if(x>r||x<l)return;//无交集
	id=clone(id);
	if(l==r){
		t[id].cnt+=val;
		return;
	}
	int mid=(l+r)>>1;
	update(t[id].ls,l,mid,x,val);
	update(t[id].rs,mid+1,r,x,val);
	up(id);
}
int query(vector<int> p,vector<int> q,int l,int r,int k){//root l-1,root r
	//树状数组需要p，因为需要统计[1,l-1]和[1,r]的贡献
	if(l==r)return l;
	int c=0,lcnt=0,rcnt=0;
	for(auto i:p)lcnt+=t[t[i].ls].cnt;
	for(auto i:q)rcnt+=t[t[i].ls].cnt;
	c=rcnt-lcnt;
	int mid=(l+r)>>1;
	if(k<=c){
		for(int i=0;i<p.size();i++)p[i]=t[p[i]].ls;
		for(int i=0;i<q.size();i++)q[i]=t[q[i]].ls;
		return query(p,q,l,mid,k);
	}
	else{
		for(int i=0;i<p.size();i++)p[i]=t[p[i]].rs;
		for(int i=0;i<q.size();i++)q[i]=t[q[i]].rs;
		return query(p,q,mid+1,r,k-c);
	}
}
int query2(vector<int> p,vector<int> q,int l,int r,int ql,int qr){//查询[ql,qr]区间内的数的个数
    if(ql>r||qr<l)return 0;
    int lcnt=0,rcnt=0;
    for(auto i:p)lcnt+=t[i].cnt;
    for(auto i:q)rcnt+=t[i].cnt;
    if(ql<=l&&r<=qr){
        return rcnt-lcnt;
    }
    int mid=(l+r)>>1;
    vector<int> lp,lq,rp,rq;
    for(auto i:p){
        lp.push_back(t[i].ls);
        rp.push_back(t[i].rs);
    }
    for(auto i:q){
        lq.push_back(t[i].ls);
        rq.push_back(t[i].rs);
    }
    return query2(lp,lq,l,mid,ql,qr)+query2(rp,rq,mid+1,r,ql,qr);
}
int lowbit(int x){return x&-x;}
void modify(int x,int y,int val){
	int gy=getrank(y);
	for(int i=x;i<=n;i+=lowbit(i)){
		update(root[i],1,tot2,gy,val);
	}
}
int ask(int l,int r,int k){//查询排名为k的数（区间内第k小的数）
	vector<int> p,q;
	for(int i=l-1;i;i-=lowbit(i))p.push_back(root[i]);
	for(int i=r;i;i-=lowbit(i))q.push_back(root[i]);
	return query(p,q,1,tot2,k);
}
int ask2(int l,int r,int k){//查询区间内小于等于k的数的个数
    vector<int> p,q;
    for(int i=l-1;i;i-=lowbit(i))p.push_back(root[i]);
    for(int i=r;i;i-=lowbit(i))q.push_back(root[i]);
    int g=getrank(k);
    if(g<1)return 0;
    return query2(p,q,1,tot2,1,g);
}
void lsh(){
	sort(b+1,b+tot2+1);
	tot2=unique(b+1,b+tot2+1)-b-1;
}
struct op{
	int type,a,b,c;
	op(){a=b=c=0;}
	op(char tp,int l,int r,int k){type=tp,a=l,b=r,c=k;}
	op(char tp,int x,int y){type=tp,a=x,b=y;}
}opr[maxn];
int optot=0,sroot;
void build2(int N){for(int i=1;i<=N;i++)modify(i,a[i],1);}//插入
void del(int x,int v){modify(x,v,-1);}
void ins(int x,int v){modify(x,v,1);}
void change(int pos,int k){
	del(pos,a[pos]);
	a[pos]=k;
	ins(pos,a[pos]);
}
int kth(int l,int r,int k){return getnum(ask(l,r,k));}//查询排名为k的数
int q_rank(int l,int r,int x){
    return ask2(l,r,x-1);
}
int pre(int l,int r,int x){
    int rk=q_rank(l,r,x-1);//严格小于x的排名
    if(!rk)return INT_MIN;;
    return kth(l,r,rk);
}
int suf(int l,int r,int x){
    int rk=q_rank(l,r,x)+1;//严格大于x的排名
    if(rk>r-l+1)return INT_MAX;
    return kth(l,r,rk);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[++tot2]=a[i];
	}
	for(int i=1;i<=m;i++){
		int opt,l,r,k,pos;
		cin>>opt;
		if(opt==1){//ranking
			cin>>l>>r>>k;
			opr[++optot]=op(1,l,r,k);
		}
		else if(opt==2){//k-th
			cin>>l>>r>>k;
			opr[++optot]=op(2,l,r,k);
		}
		else if(opt==3){//modify
			cin>>pos>>k;
			opr[++optot]=op(3,pos,k);
			b[++tot2]=k;
		}
		else if(opt==4){
			cin>>l>>r>>k;
			opr[++optot]=op(4,l,r,k);
		}
		else if(opt==5){
			cin>>l>>r>>k;
			opr[++optot]=op(5,l,r,k);
		}
	}
	lsh();
	build(root[0],1,tot2); 
	build2(n);
	for(int i=1;i<=optot;i++){
        if(opr[i].type==1){
            int l=opr[i].a,r=opr[i].b,k=opr[i].c;
            cout<<q_rank(l,r,k)<<endl;
        }
        else if(opr[i].type==2){
            int l=opr[i].a,r=opr[i].b,k=opr[i].c;
            cout<<kth(l,r,k)<<endl;
        }
		else if(opr[i].type==3){//modify
			int x=opr[i].a,y=opr[i].b;
			change(x,y);
		}
		else if(opr[i].type==4){
            int l=opr[i].a,r=opr[i].b,k=opr[i].c;
            cout<<pre(l,r,k)<<endl;
        }
        else if(opr[i].type==5){
            int l=opr[i].a,r=opr[i].b,k=opr[i].c;
            cout<<suf(l,r,k)<<endl;
			
		}
	}
	return 0;
}