朴素的线段树套Splay

求如何卡常

提交记录

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e+4+100;
const int infmax = 2147483647;
const int infmin = -2147483647;
int n,m,tot;
int a[maxn],rt[maxn<<3];
int f[maxn<<6],v[maxn<<6],ch[maxn<<6][2],size[maxn<<6],cnt[maxn<<6];

inline int read(){
	char cc = getchar(); int cn = 0, flus = 1;
	while(cc < '0' || cc > '9'){
    	if(cc == '-') flus = -flus;
		cc = getchar();
	}
	while(cc >= '0' && cc <= '9')
	    cn = cn * 10 + cc - '0', cc = getchar();
	return cn * flus;
}
inline void pushup(int x){
	size[x]=size[ch[x][0]]+size[ch[x][1]]+cnt[x];
	//printf("pushup %d %d\n",x,size[x]);
}
inline void connect(int s,int fa,int d){
	f[s] = fa;
	ch[fa][d] = s;
}
inline int get(int x){
	return ch[f[x]][1] == x;
}
inline void rotate(int x){
	int fa=f[x],gfa=f[fa];
	int s1=get(x),s2=get(fa);
	f[ch[x][s1^1]]=fa;
	ch[fa][s1]=ch[x][s1^1];
	f[x]=gfa;
	ch[gfa][s2]=x;
	f[fa]=x;
	ch[x][s1^1]=fa;
	pushup(fa);
	pushup(x);
}
inline void Splay(int o,int x,int gol){
	//printf("Splay %d %d %d\n",x,f[x],gol);
	for(int fa;(fa=f[x])&& fa!=gol;rotate(x)){
		if(f[fa]!=gol) rotate(get(x)==get(fa)?fa:x);
	}
	if(!gol) rt[o] = x;
}
inline void find(int o,int x){
	int cur=rt[o];
	if(!cur) return ;
	while(ch[cur][x>v[cur]] &&(x!=v[cur])) cur=ch[cur][x>v[cur]];
	//printf("find %d\n",v[cur])
	Splay(o,cur,0);
	//printf("find %d %d\n",cur,rt[o]); 
}
inline void new_pnt(int u,int fa,int x){
	v[u] = x;
	f[u] = fa;
	size[u] = cnt[u] = 1;
	ch[u][0]=ch[u][1]=0;
	if(fa) ch[fa][x>v[fa]] = u;
	pushup(u);
}
inline void ins(int o,int x){
	//printf("ins %d %d\n",o,x);
	int cur=rt[o],fa=0;
	if(!cur){
		cur=++tot;
		v[cur]=x;
		f[cur]=fa;
		ch[cur][0]=ch[cur][1]=0;
		size[cur]=cnt[cur]=1;
		rt[o]=cur;
		return ;
	}
	while(cur&& (v[cur]!=x)){
		fa=cur;
		cur=ch[cur][x>v[cur]];
	}
	if(cur){
		++cnt[cur];
	}
	else{
		cur=++tot;
		v[cur]=x;
		f[cur]=fa;
		ch[cur][0]=ch[cur][1]=0;
		size[cur]=cnt[cur]=1;
		if(fa) ch[fa][x>v[fa]] = cur;
	}
	//printf("ins %d\n",tot);
	Splay(o,cur,0);
}
inline int rank(int o,int x){
	find(o,x);
	//printf("rank %d %d %d\n",x,v[rt[o]],size[ch[rt[o]][0]]);
	if(v[rt[o]]>=x) return size[ch[rt[o]][0]]-1 ;
	return size[ch[rt[o]][0]]+cnt[rt[o]]-1;
}
inline int pre(int o,int x){
	find(o,x);
	int u=rt[o];
	//printf("pre %d %d\n",v[u],x);
	if(v[u]<x) return u;
	u=ch[u][0];
	while(ch[u][1]) u=ch[u][1];
	return u;
}
inline int suc(int o,int x){
	find(o,x);
	int u=rt[o];
	if(v[u]>x) return u;
	u=ch[u][1];
	while(ch[u][0]) u=ch[u][0];
	return u;
}
inline void del(int o,int x){
	int lst=pre(o,x);
	//printf("del\n");
	int nxt=suc(o,x);
	//printf("del %d %d\n",lst,nxt);
	Splay(o,lst,0);
	//printf("del\n");
	Splay(o,nxt,lst);
	if(cnt[ch[nxt][0]]>1){
		--cnt[ch[nxt][0]];
		Splay(o,ch[nxt][0],0); 
	}
	else{
		ch[nxt][0]=0;
		pushup(nxt);
		pushup(lst);
	}
}


inline void seg_init(int o,int l,int r){
	//printf("seginit %d %d %d\n",o,l,r);
	ins(o,infmax);ins(o,infmin);
	if(l==r) return ;
	int mid=l+r>>1;
	seg_init(o<<1,l,mid);
	seg_init(o<<1|1,mid+1,r);
}
inline void seg_ins(int o,int l,int r,int q,int x){
	ins(o,x);
	if(l==r) return ;
	int mid=(l+r)>>1;
	if(q<=mid) seg_ins(o<<1,l,mid,q,x);
	else seg_ins(o<<1|1,mid+1,r,q,x);
}
inline void seg_change(int o,int l,int r,int q,int x){
	del(o,a[q]);ins(o,x);
	if(l==r){
		a[q]=x;
		return;
	}
	int mid=(l+r)>>1;
	if(q<=mid) seg_change(o<<1,l,mid,q,x);
	else seg_change(o<<1|1,mid+1,r,q,x);
}
inline int seg_rank(int o,int l,int r,int ql,int qr,int k){
	//printf("segrank %d %d %d\n",o,l,r);
	if(ql>r||qr<l) return 0;
	if(ql<=l&&r<=qr){
		//printf("segrank %d %d %d\n",0,l,r);
		return rank(o,k);
	}
	int mid=l+r>>1;
	return seg_rank(o<<1,l,mid,ql,qr,k)+seg_rank(o<<1|1,mid+1,r,ql,qr,k);
}
inline int seg_kth(int ql,int qr,int k){
	int l=0,r =1e8,mid,ans;
	while(l<=r){
		mid=(l+r)>>1;
		int res=seg_rank(1,1,n,ql,qr,mid)+1;
		//printf("segkth %d %d %d %d\n",l,r,mid,res);
		if(res<=k) l=mid+1,ans=mid;
		else r=mid-1;
	}
	return ans;
}
inline int seg_pre(int o,int l,int r,int ql,int qr,int k){
	if(ql>r||qr<l) return infmin;
	if(ql<=l&&r<=qr){
		return v[pre(o,k)];
	}
	int mid=l+r>>1;
	return max(seg_pre(o<<1,l,mid,ql,qr,k),seg_pre(o<<1|1,mid+1,r,ql,qr,k));
}
inline int seg_suc(int o,int l,int r,int ql,int qr,int k){
	if(ql>r||qr<l) return infmax;
	if(ql<=l&&r<=qr){
		return v[suc(o,k)];
	}
	int mid=l+r>>1;
	return min(seg_suc(o<<1,l,mid,ql,qr,k),seg_suc(o<<1|1,mid+1,r,ql,qr,k));
}

int main(){
	//freopen("33802.in","r",stdin);
	//freopen("33802.out","w",stdout);
	cin>>n>>m;
	seg_init(1,1,n);
	for(int i=1;i<=n;++i){
		a[i]=read();
		seg_ins(1,1,n,i,a[i]);
	}
	while(m--){
		int opt,l,r,k;
		opt=read(),l=read(),r=read();
		if(opt==1) k=read(),printf("%d\n",seg_rank(1,1,n,l,r,k)+1);
		if(opt==2) k=read(),printf("%d\n",seg_kth(l,r,k));
		if(opt==3) seg_change(1,1,n,l,r);
		if(opt==4) k=read(),printf("%d\n",seg_pre(1,1,n,l,r,k));
		if(opt==5) k=read(),printf("%d\n",seg_suc(1,1,n,l,r,k));
	}
	return 0;
}