此博客停更

泥是不是啥叼，这种题现在才做

是是是，您教导的是

传送门-->http://www.lydsy.com/JudgeOnline/problem.php?id=3196

这题怎么套都可以吧。。线段树套平衡树，线段树套线段树，平衡树套平衡树？

然而我并没这样写，我写浪一点直接就树状数组套权值线段树上了

似乎$rank$靠前的都是这个？或许有什么特技吧

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 50005
struct tree{tree*l,*r;int cnt;}*T[N],C[N*200],*c=C,*L[33],*R[33];
int i,j,m,n,x,y,M,f[N],l[N],r[N],k[N],a[N],hs[N<<1];
#define nc() getchar()
inline int read(){
	int f=1,x=0;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
	if(ch=='-')ch=nc(),f=-1;for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f;
}
#define lson o->l,l,m
#define rson o->r,m+1,r
void add(tree*&o,int l,int r,int v,int f){
	if(o==NULL)o=++c;o->cnt+=f;if(l==r)return;int m=l+r>>1;
	v<=m?add(lson,v,f):add(rson,v,f);
}
inline void Add(int x,int d,int f){for(;x<=n;x+=x&-x)add(T[x],1,M,d,f);}
inline int askkth(int x,int y,int l,int r,int v){
	int h=0,t=0,rr=r,ll=l-1,k=0,ar=0,al=0,i,m=x+y>>1;
	for(;rr;rr-=rr&-rr)R[++t]=T[rr];
	for(;ll;ll-=ll&-ll)L[++h]=T[ll];
	for(;x<y;m=x+y>>1)if(v>m){
		for(ar=0,i=1;i<=t;R[i]=R[i]->r,++i){
			if(R[i]->l!=NULL)ar+=R[i]->l->cnt;
			if(R[i]->r==NULL)R[i]->r=++c;
		}
		for(al=0,i=1;i<=h;L[i]=L[i]->r,++i){
			if(L[i]->l!=NULL)al+=L[i]->l->cnt;
			if(L[i]->r==NULL)L[i]->r=++c;
		}
		k+=ar-al,x=m+1;
	}else{
		for(i=1;i<=t;R[i]=R[i]->l,++i)if(R[i]->l==NULL)R[i]->l=++c;
		for(i=1;i<=h;L[i]=L[i]->l,++i)if(L[i]->l==NULL)L[i]->l=++c;y=m;
	}
	return k+1;
}
inline int askknm(int x,int y,int l,int r,int k){
	int h=0,t=0,rr=r,ll=l-1,ar=0,al=0,i,m=x+y>>1,sm=0;
	for(;rr;rr-=rr&-rr)R[++t]=T[rr];
	for(;ll;ll-=ll&-ll)L[++h]=T[ll];
	for(;x<y&&k;m=x+y>>1){
		for(ar=0,i=1;i<=t;++i)if(R[i]->l!=NULL)ar+=R[i]->l->cnt;
		for(al=0,i=1;i<=h;++i)if(L[i]->l!=NULL)al+=L[i]->l->cnt;
		if(ar-al>=k){
			for(i=1;i<=t;R[i]=R[i]->l,++i)if(R[i]->l==NULL)R[i]->l=++c;
			for(i=1;i<=h;L[i]=L[i]->l,++i)if(L[i]->l==NULL)L[i]->l=++c;y=m;
		}else{
			for(i=1;i<=t;R[i]=R[i]->r,++i)if(R[i]->r==NULL)R[i]->r=++c;
			for(i=1;i<=h;L[i]=L[i]->r,++i)if(L[i]->r==NULL)L[i]->r=++c;x=m+1,k-=ar-al;
		}
	}
	return x;
}
int main(){
	for(n=read(),m=read(),i=1;i<=n;++i)a[i]=read(),hs[++*hs]=a[i];
	for(i=1;i<=m;++i){
		f[i]=read();
		if(f[i]!=3&&f[i]!=2)l[i]=read(),r[i]=read(),k[i]=read(),hs[++*hs]=k[i];
		else if(f[i]==3)l[i]=read(),k[i]=read(),hs[++*hs]=k[i];
		else l[i]=read(),r[i]=read(),k[i]=read();
	}
	sort(hs+1,hs+*hs+1),M=unique(hs+1,hs+*hs+1)-hs-1;
	for(i=1;i<=n;++i)a[i]=lower_bound(hs+1,hs+M+1,a[i])-hs;
	for(i=1;i<=m;++i)if(f[i]!=3&&f[i]!=2)k[i]=lower_bound(hs+1,hs+M+1,k[i])-hs;
	else if(f[i]==3)k[i]=lower_bound(hs+1,hs+M+1,k[i])-hs;
	for(i=1;i<=n;++i)Add(i,a[i],1);
	for(i=1;i<=m;++i){
		if(f[i]==1)printf("%d\n",askkth(1,M,l[i],r[i],k[i]));
		if(f[i]==2)printf("%d\n",hs[askknm(1,M,l[i],r[i],k[i])]);
		if(f[i]==3)Add(l[i],a[l[i]],-1),Add(l[i],k[i],1),a[l[i]]=k[i];
		if(f[i]==4)printf("%d\n",hs[askknm(1,M,l[i],r[i],askkth(1,M,l[i],r[i],k[i])-1)]);
		if(f[i]==5)printf("%d\n",hs[askknm(1,M,l[i],r[i],askkth(1,M,l[i],r[i],k[i]+1))]);
	}
}

$loading...$