社区讨论

BST 还是WA 只有28分,这波调不出来了

P3369【模板】普通平衡树参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mhz4c3lp
此快照首次捕获于
2025/11/15 01:15
4 个月前
此快照最后确认于
2025/11/16 13:51
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
//#define int long long
//#define lc p<<1
//#define rc p<<1|1
//#define lowbit(x) x&-x
#define endl putchar('\n')
#define psp putchar(' ')
using namespace std;
const int N=1e6+5;
const int M=1e3+5;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
	return x*f;
}
void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x<10){putchar(x+'0');return;}
	print(x/10);
	putchar(x%10+'0');
}
void putstr(string s){
	for(int i=0;i<s.size();i++)putchar(s[i]);
}
int n,m,k;
int T;
int cnt;
struct node{
	int l,r,cnt,ans,flag;
	int lans;
}f[N];
int Pre;
int Suc;
void add(int p,int x){
	if(!f[p].flag){
		f[++cnt]=node{0,0,1,x,1,0};
		return;
	}
	if(x>f[p].ans){
		if(f[f[p].r].flag){
			add(f[p].r,x);
		}
		else{
			f[++cnt]=node{0,0,1,x,1,0};
			f[p].r=cnt;
		}
	}	
	else if(x<f[p].ans){
		f[p].lans++;
		if(f[f[p].l].flag){
			add(f[p].l,x);
		}
		else{
			f[++cnt]=node{0,0,1,x,1,0};
			f[p].l=cnt;
		}
	}
	else f[p].cnt++;
}
int getmin(int p){
	if(f[f[p].l].flag)return getmin(f[p].l);
	else return p;
}
bool remove(int p,int x){
	if(!f[p].flag)return 0;
	if(f[p].ans==x){
		if(f[p].cnt>1)f[p].cnt--;
		else{
			if(f[f[p].l].flag&&f[f[p].r].flag){
				int q=getmin(f[p].r);
				f[p].cnt=f[q].cnt;
				f[p].ans=f[q].ans;
				f[q].cnt=1;
				remove(f[p].r,f[q].ans);
			}
			else if(f[f[p].l].flag)f[p]=f[f[p].l];
			else if(f[f[p].r].flag)f[p]=f[f[p].r];
			else f[p].flag=0;
		}
		return 1;
	}
	else if(x>f[p].ans){
		return remove(f[p].r,x);
	}
	else{
		bool glaf=remove(f[p].l,x);
		if(glaf)f[p].lans--;
		return glaf;
	}
}
int ranking(int p,int x){
	if(!f[p].flag){
		return 1;
	}
	if(f[p].ans==x){
		return f[p].lans+1;
	}
	else if(x>f[p].ans){
		return f[p].lans+f[p].cnt+ranking(f[p].r,x);
	}
	else{
		return ranking(f[p].l,x);
	}
}
int query(int p,int x){
	if(x==0)return f[p].ans;
	if(f[p].lans<x){
		return query(f[p].r,x-f[p].lans-1);
	}
	else if(f[p].lans==x){
		return f[p].ans;
	}
	return query(f[p].l,x);
}
void pre(int p,int x){
	if(!f[p].flag)return;
	if(f[p].ans<x){
		Pre=f[p].ans;
		pre(f[p].r,x);
	}
	else{
		pre(f[p].l,x);
	}
}
void suc(int p,int x){
	if(!f[p].flag)return;
	if(f[p].ans>x){
		Suc=f[p].ans;
		suc(f[p].l,x);
	}
	else{
		suc(f[p].r,x);
	}
}
signed main(){
//	freopen("in.txt","r",stdin);
	//ios::sync_with_stdio(0);
	m=read();
	while(m--){
		int op=read(),x=read();
		if(op==1){
			add(1,x);
		}
		else if(op==2){
			remove(1,x);
		}
		else if(op==3){
			print(ranking(1,x)),endl;
		}
		else if(op==4){
			print(query(1,x-1)),endl;
		}
		else if(op==5){
			pre(1,x);
			print(Pre),endl;
		}
		else{
			suc(1,x);
			print(Suc),endl;
		}
	}
}

回复

2 条回复,欢迎继续交流。

正在加载回复...