社区讨论
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 条回复,欢迎继续交流。
正在加载回复...