话说 splay 过不了这模板题吗(splay挂了)(悲
查看原帖
话说 splay 过不了这模板题吗(splay挂了)(悲
580107
xixisuper楼主2023/1/14 21:42

16分,前两个点对了,其他的点 T 了

哼哼啊啊啊啊

#include <iostream>
#define ll long long 
using namespace std;
const ll N=1e6+10;

inline ll read(){
	ll x,y;
	char c=getchar();
	x=0,y=1;
	while(c<'0'||c>'9') {if(c=='-') y=-1;c=getchar();}
	while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*y;
}

ll data[N];
ll ch[N][2];
ll fa[N];
ll root;
ll tot;
ll sum[N];
ll cnt[N];

void update(ll x){
	sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+cnt[x];
}

ll get_wh(ll x){
	if(ch[fa[x]][0]==x) return 0;
	return 1;
}
 
void rotate(ll x){
	ll y=fa[x],z=fa[y],k=get_wh(x);
	fa[x]=z;
	ch[z][get_wh(y)]=x;
	fa[ch[x][k^1]]=y;
	ch[y][k]=ch[x][k^1];
	fa[y]=x;
	ch[x][k^1]=y;
	update(y);update(x);
}

void splay(ll x,ll target){
	while(fa[x]!=target){
		ll y=fa[x],z=fa[y];
		if(z!=target){
			if(get_wh(x)==get_wh(y)) rotate(y);
			else rotate(x);
		}
		rotate(x);
	}
	if(!target) root=x;
}

void insert_(ll v){
	ll x=root,y=0;
	while(x&&data[x]!=v){
		y=x;
		x=ch[x][v>data[x]];
	}
	if(x) cnt[x]++;
	else{
		x=++tot;
		if(y) ch[y][v>data[y]]=x;
		ch[x][0]=ch[x][1]=0;
		fa[x]=y;data[x]=v;cnt[x]=1;sum[x]=1;
	}
	splay(x,0);
}

void find_splay(ll v){
	ll x=root;
	if(!x) return;
	while(ch[x][v>data[x]]&&v!=data[x]){
		x=ch[x][v>data[x]];
	}
	splay(x,0);
}

ll pn_pos(ll v,ll f){//若 f=0 则为找前驱,否则为找后继 
	find_splay(v);
	ll x=root;
	if(data[x]>v&&f) return x;
	if(data[x]<v&&!f) return x;
	x=ch[x][f];
	while(ch[x][f^1]) x=ch[x][f^1];
	return x; 
} 

void del(ll v){
	ll pre=pn_pos(v,0),nxt=pn_pos(v,1);
	splay(pre,0);splay(nxt,pre);
	ll x=ch[nxt][0];
	if(cnt[x]>1) cnt[x]--,splay(x,0);
	else{
		ch[nxt][0]=0;
		fa[x]=0;
		splay(nxt,0);
	}
}

ll kth(ll k){
	ll x=root;
	if(sum[x]<k) return 0;
	while(1){
		ll lc=ch[x][0];
		if(k>sum[lc]+cnt[x]){
			k-=(sum[lc]+cnt[x]);
			x=ch[x][1]; 
		}
		else{
			if(sum[lc]>=k) x=lc;
			else return data[x]; 
		}
	}
}

ll getrank(ll v){
	ll x=root,rank=0;
	while(x){
		if(data[x]<v){
			rank+=sum[ch[x][0]]+cnt[x];
			x=ch[x][1];
		}
		else x=ch[x][0];
	}
	return rank+1;
}

ll n;

int main(){
	ll opt,x;
	n=read();
	while(n--){
		opt=read();
		x=read();
		if(opt==1){
			insert_(x);
		}
		if(opt==2){
			del(x);
		}
		if(opt==3){
			printf("%lld\n",getrank(x));
		}
		if(opt==4){
			printf("%lld\n",kth(x));
		}
		if(opt==5){
			printf("%lld\n",data[pn_pos(x,0)]);
		}
		if(opt==6){
			printf("%lld\n",data[pn_pos(x,1)]);
		}
	}
	return 0;
}

样例过了的

自己的测试数据也过了的

但为什么 T 了(悲悲悲悲悲悲悲

大佬如果发现有错的地方请指正

没有错的地方请帮忙卡常

2023/1/14 21:42
加载中...