开o2总用时能优化7秒

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,a[N],sz;
namespace nqio{const unsigned R=4e5,W=4e5;char*a,*b,i[R],o[W],*c=o,*d=o+W,h[40],*p=h,y;bool s;struct q{void r(char&x){x=a==b&&(b=(a=i)+fread(i,1,R,stdin),a==b)?-1:*a++;}void f(){fwrite(o,1,c-o,stdout);c=o;}~q(){f();}void w(char x){*c=x;if(++c==d)f();}q&operator>>(char&x){do r(x);while(x<=32);return*this;}q&operator>>(char*x){do r(*x);while(*x<=32);while(*x>32)r(*++x);*x=0;return*this;}template<typename t>q&operator>>(t&x){for(r(y),s=0;!isdigit(y);r(y))s|=y==45;if(s)for(x=0;isdigit(y);r(y))x=x*10-(y^48);else for(x=0;isdigit(y);r(y))x=x*10+(y^48);return*this;}q&operator<<(char x){w(x);return*this;}q&operator<<(char*x){while(*x)w(*x++);return*this;}q&operator<<(const char*x){while(*x)w(*x++);return*this;}template<typename t>q&operator<<(t x){if(!x)w(48);else if(x<0)for(w(45);x;x/=10)*p++=48|-(x%10);else for(;x;x/=10)*p++=48|x%10;while(p!=h)w(*--p);return*this;}}qio;}using nqio::qio;
struct kzlb{
	vector<vector<int> >v;vector<int>_;
	int fd(int x){
		int i,lst=-0x7fffffff;
		for(i=0;i<v.size();++i){
			if(lst<x&&x<=v[i].back())return i;
			lst=v[i].back();
		}
		return v.size()-1;
	}
	void ins(int x){
		if(!v.size())return v.push_back(_),v[0].push_back(x),void();
		int p=fd(x);
		v[p].insert(lower_bound(v[p].begin(),v[p].end(),x),x);
		if(v[p].size()>2*sz){
			vector<int>temp(v[p].end()-sz,v[p].end());v[p].erase(v[p].end()-sz,v[p].end());
			v.insert(v.begin()+p+1,temp);
		}
	}
	void era(int x){
		int p=fd(x);
		v[p].erase(lower_bound(v[p].begin(),v[p].end(),x));
		if(!v[p].size())v.erase(v.begin()+p);
	}
	int low(int x){
		int i,p=fd(x),res=1;
		for(i=0;i<p;++i)res+=v[i].size();
		return res+lower_bound(v[p].begin(),v[p].end(),x)-v[p].begin()-1;
	}
	int low2(int x){
		int i,p=fd(x),res=1;
		for(i=0;i<p;++i)res+=v[i].size();
		return res+upper_bound(v[p].begin(),v[p].end(),x)-v[p].begin()-1;
	}
}tree[N<<2];
void bd(int l,int r,int p){
	if(l==r)return tree[p].ins(a[l]),void();
	int i,j,mid=l+r>>1;
	bd(l,mid,p<<1),bd(mid+1,r,p<<1|1);
	for(i=0;i<tree[p<<1].v.size();++i)for(j=0;j<tree[p<<1].v[i].size();++j)tree[p].ins(tree[p<<1].v[i][j]);
	for(i=0;i<tree[p<<1|1].v.size();++i)for(j=0;j<tree[p<<1|1].v[i].size();++j)tree[p].ins(tree[p<<1|1].v[i][j]); 
}
void upd(int s,int t,int c,int d,int l,int r,int p){
	tree[p].era(c),tree[p].ins(d);
	if(s<=l&&r<=t)return ;
	int mid=l+r>>1;
	if(s<=mid)upd(s,t,c,d,l,mid,p<<1);
	if(t>mid)upd(s,t,c,d,mid+1,r,p<<1|1);
}
int qrk(int s,int t,int c,int l,int r,int p){
	if(s<=l&&r<=t)return tree[p].low(c);
	int mid=l+r>>1,res=0;
	if(s<=mid)res+=qrk(s,t,c,l,mid,p<<1);
	if(t>mid)res+=qrk(s,t,c,mid+1,r,p<<1|1);
	return res; 
}
int kth(int x,int y,int k){
	int l=0,r=1e8,mid,res=0;
	while(l<=r){
		if(mid=l+r>>1,qrk(x,y,mid,1,n,1)+1<=k)res=mid,l=mid+1;
		else r=mid-1;
	}
	return res;
}
int qrk2(int s,int t,int c,int l,int r,int p){
	if(s<=l&&r<=t)return tree[p].low2(c);
	int mid=l+r>>1,res=0;
	if(s<=mid)res+=qrk2(s,t,c,l,mid,p<<1);
	if(t>mid)res+=qrk2(s,t,c,mid+1,r,p<<1|1);
	return res; 
}
int pre(int l,int r,int x){
	int p=qrk(l,r,x,1,n,1);
	return !p?-0x7fffffff:kth(l,r,p);
}
int nxt(int l,int r,int x){
	int p=qrk2(l,r,x,1,n,1);
	return p==r-l+1?0x7fffffff:kth(l,r,p+1);
}
int main(){
//	freopen("1.txt","r",stdin);
	int i,m,op,x,y,z;
	qio>>n>>m,sz=sqrt(n);
	for(i=1;i<=n;++i)qio>>a[i];
	bd(1,n,1); 
	while(m--){
		qio>>op>>x>>y;
		if(op==1)qio>>z,qio<<qrk(x,y,z,1,n,1)+1<<'\n';
		if(op==2)qio>>z,qio<<kth(x,y,z)<<'\n';
		if(op==3)upd(x,x,a[x],y,1,n,1),a[x]=y;
		if(op==4)qio>>z,qio<<pre(x,y,z)<<'\n';
		if(op==5)qio>>z,qio<<nxt(x,y,z)<<'\n';
	}
}