Splay 本地编译通过,你谷上 CE 求助
查看原帖
Splay 本地编译通过,你谷上 CE 求助
160150
WxjzKK楼主2023/10/5 13:45
//【模板】Splay 
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline void read(int &n){
	int s=0,t=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') t=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		s=(s<<3)+(s<<1)+(c^48);c=getchar();
	}
	n=s*t;
}
inline void put(int n){
	if(n<0){
		putchar('-');n=-n;
	}
	if(n<10){
		putchar(n+48);return;
	}
	put(n/10);
	putchar(n%10+48);
}
struct node{
	int fa,val,siz,cnt,son[2];
}t[MAXN];
int root,tot;
inline int wson(int rt){
	return t[t[rt].fa].son[1]==rt;
}
inline void update(int rt){
	t[rt].siz=t[rt].cnt+t[t[rt].son[0]].siz+t[t[rt].son[1]].siz;
}
inline void clear(int rt){
	t[rt].cnt=t[rt].fa=t[rt].siz=t[rt].son[0]=t[rt].son[1]=t[rt].val=0;
}
inline void rotate(int rt){
	int fa=t[rt].fa,gfa=t[fa].fa,ws=wson(rt),wsf=wson(fa);
	t[fa].son[ws]=t[rt].son[ws^1];
	t[t[fa].son[ws]].fa=fa;
	t[rt].son[ws^1]=fa;
	t[fa].fa=rt;t[rt].fa=gfa;
	if(gfa) t[gfa].son[wsf]=rt;
	update(fa);update(rt);
}
inline void Splay(int rt){
	for(register int fa=t[rt].fa;(fa=t[rt].fa)&&fa;rotate(rt))
		if(t[fa].fa) rotate(wson(rt)==wson(fa)?fa:rt);
	root=rt;
}
inline void precursor(){
	int cur=t[root].son[0];
	if(!cur) return;
	while(t[cur].son[1]) cur=t[cur].son[1];
	Splay(cur);
}
inline void successor(){
	int cur=t[root].son[1];
	if(!cur) return;
	while(t[cur].son[0]) cur=t[cur].son[0];
	Splay(cur);
}
inline void insert(int &rt,int fa,int x){
	if(!rt){
		rt=++tot;
		t[rt].val=x;++t[rt].cnt;t[rt].fa=fa;
		update(rt);
		if(fa){
			t[fa].son[t[fa].val<x]=rt;update(fa);
		}
		Splay(rt);return;
	}
	if(t[rt].val==x){
		++t[rt].cnt;
		update(rt);
		if(t[rt].fa) update(fa);
		Splay(rt);return;
	}
	else insert(t[rt].son[t[rt].val<x],rt,x);
}
inline void remove(int rt,int x){
	if(t[rt].val>x) remove(t[rt].son[0],x);
	else if(t[rt].val<x) remove(t[rt].son[1],x);
	else{
		Splay(rt);
		if(t[rt].cnt>1){
			--t[rt].cnt;update(rt);return;
		}
		else if(!t[rt].son[0]&&!t[rt].son[1]){
			root=0;clear(rt);return;
		}
		else if(!t[rt].son[0]){
			root=t[rt].son[1];t[root].fa=0;clear(rt);return;
		}
		else if(!t[rt].son[1]){
			root=t[rt].son[0];t[root].fa=0;clear(rt);return;
		}
		else{
			precursor();
			t[t[rt].son[1]].fa=root;
			t[root].son[1]=t[rt].son[1];
			clear(rt);update(rt);
		}
	}
}
inline int rank(int rt,int x){
	if(t[rt].val>x) return rank(t[rt].son[0],x);
	else if(t[rt].val<x) return t[t[rt].son[0]].siz+t[rt].cnt+rank(t[rt].son[1],x);
	else return t[t[rt].son[0]].siz+1;
}
inline int kth(int rt,int x){
	if(t[t[rt].son[0]].siz>=x) return kth(t[rt].son[0],x);
	else if(t[rt].siz+t[t[rt].son[1]].siz<x) return kth(t[rt].son[1],x-t[rt].siz-t[t[rt].son[0]].siz);
	else return t[rt].val;
}
int main(){
	int n,opt,x;
	read(n);
	for(register int i=1;i<=n;++i){
		read(opt);read(x);
		if(opt==1) insert(root,0,x);
		else if(opt==2) remove(root,x);
		else if(opt==3){
			put(rank(root,x));putchar('\n');
		}
		else if(opt==4){
			put(kth(root,x));putchar('\n');
		}
		else if(opt==5){
			insert(root,0,x);precursor();put(t[root].val);putchar('\n');remove(root,x);
		}
		else{
			insert(root,0,x);successor();put(t[root].val);putchar('\n');remove(root,x);
		}
	}
	return 0;
}

本地用的 Dev-C++ 5.11,洛谷上用的 C++14(GCC 9),然后 CE,上了洛谷的 在线IDE 显示我的 rank 函数使用有歧义,求助。

2023/10/5 13:45
加载中...