已AC 求简化代码
- 板块P3369 【模板】普通平衡树
- 楼主ABCgfed
- 当前回复2
- 已保存回复2
- 发布时间2024/8/18 21:34
- 上次更新2024/8/19 09:39:48
查看原帖
被骇客银狼阻止的越权访问保存失败
已AC 求简化代码
#include<iostream>
using namespace std;
struct node{
int val;
int fa;
int lc;
int rc;
int het;
int num;
}tree[700000];
int topt=0;
int root=0;
int que=0;
void leftrotate(int p){
int ifr=1;
if(tree[tree[p].fa].rc==p)tree[tree[p].fa].rc=tree[p].rc,ifr=0;
if(tree[tree[p].fa].lc==p)tree[tree[p].fa].lc=tree[p].rc,ifr=0;
int rec=tree[tree[p].rc].lc;
tree[tree[p].rc].lc=p;
tree[tree[p].rc].fa=tree[p].fa;
tree[rec].fa=p;
tree[p].fa=tree[p].rc;
tree[p].rc=rec;
tree[p].het=max(tree[tree[p].lc].het+1,tree[tree[p].rc].het+1);
tree[tree[p].fa].het=max(tree[tree[tree[p].fa].lc].het+1,tree[tree[tree[p].fa].rc].het+1);
if(ifr==0)tree[tree[tree[p].fa].fa].het=max(tree[tree[tree[tree[p].fa].fa].lc].het+1,tree[tree[tree[tree[p].fa].fa].rc].het+1);
tree[p].num=tree[tree[p].lc].num+tree[tree[p].rc].num+1;
tree[tree[p].fa].num=tree[tree[tree[p].fa].lc].num+tree[tree[tree[p].fa].rc].num+1;
if(ifr==0)tree[tree[tree[p].fa].fa].num=tree[tree[tree[tree[p].fa].fa].lc].num+tree[tree[tree[tree[p].fa].fa].rc].num+1;
if(ifr==1)root=tree[p].fa;
}
void rightrotate(int p){
int ifr=1;
if(tree[tree[p].fa].rc==p)tree[tree[p].fa].rc=tree[p].lc,ifr=0;
if(tree[tree[p].fa].lc==p)tree[tree[p].fa].lc=tree[p].lc,ifr=0;
int rec=tree[tree[p].lc].rc;
tree[tree[p].lc].rc=p;
tree[tree[p].lc].fa=tree[p].fa;
tree[rec].fa=p;
tree[p].fa=tree[p].lc;
tree[p].lc=rec;
tree[p].het=max(tree[tree[p].lc].het+1,tree[tree[p].rc].het+1);
tree[tree[p].fa].het=max(tree[tree[tree[p].fa].lc].het+1,tree[tree[tree[p].fa].rc].het+1);
if(ifr==0)tree[tree[tree[p].fa].fa].het=max(tree[tree[tree[tree[p].fa].fa].lc].het+1,tree[tree[tree[tree[p].fa].fa].rc].het+1);
tree[p].num=tree[tree[p].lc].num+tree[tree[p].rc].num+1;
tree[tree[p].fa].num=tree[tree[tree[p].fa].lc].num+tree[tree[tree[p].fa].rc].num+1;
if(ifr==0)tree[tree[tree[p].fa].fa].num=tree[tree[tree[tree[p].fa].fa].lc].num+tree[tree[tree[tree[p].fa].fa].rc].num+1;
if(ifr==1)root=tree[p].fa;
}
void check(int p,int ty){
tree[p].het=max(tree[tree[p].lc].het+1,tree[tree[p].rc].het+1);
if(tree[tree[tree[p].lc].lc].het-1>tree[tree[p].rc].het) rightrotate(p);
if(tree[tree[tree[p].rc].rc].het-1>tree[tree[p].lc].het) leftrotate(p);
if(tree[tree[tree[p].lc].rc].het-1>tree[tree[p].rc].het) leftrotate(tree[p].lc),rightrotate(p);
if(tree[tree[tree[p].rc].lc].het-1>tree[tree[p].rc].het) rightrotate(tree[p].rc),leftrotate(p);
if(tree[p].fa&&ty==0)check(tree[p].fa,ty);
}
void ins(int k,int p){
if(root==0){
topt++;
root=topt;
tree[topt].fa=0;
tree[topt].het=1;
tree[topt].lc=0;
tree[topt].rc=0;
tree[topt].num=1;
tree[topt].val=k;
return;
}
if(tree[p].val>=k&&tree[p].lc>0)tree[p].num++,ins(k,tree[p].lc);
else if(tree[p].val<k&&tree[p].rc>0)tree[p].num++,ins(k,tree[p].rc);
else if(tree[p].val>=k){
topt++;
tree[topt].fa=p;
tree[topt].het=1;
tree[topt].lc=0;
tree[topt].rc=0;
tree[topt].num=1;
tree[topt].val=k;
tree[p].num++;
tree[p].lc=topt;
// if(tree[p].het==0)tree[p].het++;
}
else{
topt++;
tree[topt].fa=p;
tree[topt].het=1;
tree[topt].lc=0;
tree[topt].rc=0;
tree[topt].num=1;
tree[topt].val=k;
tree[p].num++;
tree[p].rc=topt;
//if(tree[p].het==0)tree[p].het++;
}
check(p,0);
return;
}
void del(int k,int p){
// cout<<k<<")))"<<p<<" "<<tree[p].val<<endl;;
if(tree[p].val==k){
if(tree[p].lc==0&&tree[p].rc==0){
if(p==root){
root=0;
return;
}
if(tree[tree[p].fa].lc==p){
tree[tree[p].fa].lc=0;
tree[tree[p].fa].het=tree[tree[tree[p].fa].rc].het+1;
}
if(tree[tree[p].fa].rc==p){
tree[tree[p].fa].rc=0;
tree[tree[p].fa].het=tree[tree[tree[p].fa].lc].het+1;
}
}
else if(tree[p].rc!=0){
int j=tree[p].rc;
while(tree[j].lc){
j=tree[j].lc;
}
if(tree[j].rc&&tree[j].fa!=p){
tree[tree[j].rc].fa=tree[j].fa;
tree[tree[j].fa].lc=tree[j].rc;
tree[tree[j].fa].het=max(tree[tree[j].rc].het+1,tree[tree[tree[j].fa].rc].het+1);
}
else if(tree[j].rc==0&&tree[j].fa!=p){
tree[tree[j].fa].lc=0;
tree[tree[j].fa].het=tree[tree[tree[j].fa].rc].het+1;
}
else if(tree[j].rc&&tree[j].fa==p){
tree[tree[j].rc].fa=tree[j].fa;
tree[tree[j].fa].rc=tree[j].rc;
tree[tree[j].fa].het=max(tree[tree[j].lc].het+1,tree[tree[tree[j].fa].lc].het+1);
}
else if(tree[j].rc==0&&tree[j].fa==p){
tree[tree[j].fa].rc=0;
tree[tree[j].fa].het=1;
}
tree[p].val=tree[j].val;
while(1){
j=tree[j].fa;
tree[j].num=tree[tree[j].lc].num+tree[tree[j].rc].num+1;
tree[j].het=max(tree[tree[j].lc].het+1,tree[tree[j].rc].het+1);
check(j,1);
if(j==p)break;
}
}
else if(tree[p].lc!=0){
int j=tree[p].lc;
while(tree[j].rc){
j=tree[j].rc;
}
// cout<<j<<"(("<<tree[j].fa<<" "<<tree[j].lc<<endl;
if(tree[j].lc&&tree[j].fa!=p){
tree[tree[j].lc].fa=tree[j].fa;
tree[tree[j].fa].rc=tree[j].lc;
tree[tree[j].fa].het=max(tree[tree[j].lc].het+1,tree[tree[tree[j].fa].lc].het+1);
}
else if(tree[j].lc==0&&tree[j].fa!=p){
tree[tree[j].fa].rc=0;
tree[tree[j].fa].het=tree[tree[tree[j].fa].lc].het+1;
}
else if(tree[j].lc&&tree[j].fa==p){
tree[tree[j].lc].fa=tree[j].fa;
tree[tree[j].fa].lc=tree[j].lc;
tree[tree[j].fa].het=max(tree[tree[j].lc].het+1,tree[tree[tree[j].fa].lc].het+1);
}
else if(tree[j].lc==0&&tree[j].fa==p){
tree[tree[j].fa].lc=0;
tree[tree[j].fa].het=1;
}
tree[p].val=tree[j].val;
while(1){
j=tree[j].fa;
tree[j].num=tree[tree[j].lc].num+tree[tree[j].rc].num+1;
tree[j].het=max(tree[tree[j].lc].het+1,tree[tree[j].rc].het+1);
check(j,1);
if(j==p)break;
}
}
return;
}
if(tree[p].val<k){
del(k,tree[p].rc);
tree[p].num=tree[tree[p].lc].num+tree[tree[p].rc].num+1;
//if(tree[p].val==11)cout<<tree[p].rc<<"here"<<endl;
check(p,1);
return;
}
if(tree[p].val>k){
del(k,tree[p].lc);
tree[p].num=tree[tree[p].lc].num+tree[tree[p].rc].num+1;
check(p,1);
return;
}
return;
}
int his=0;
void dfs(int p,int ty){
if(tree[p].lc>0&&ty==1||tree[p].lc>0&&tree[p].val>=que&&ty==2||tree[p].lc>0&&que!=-1&&que<=tree[tree[p].lc].num&&ty==3){
// if(ty==1)cout<<p<<"->"<<tree[p].lc<<endl;
dfs(tree[p].lc,ty);
if(ty==3)return;
}
// if(ty==1)cout<<p<<" "<<tree[p].val<<" num"<<tree[p].num<<endl;
if(ty==3){
que-=tree[tree[p].lc].num+1;
if(que==0){
cout<<tree[p].val<<endl;//" "<<p<<" "<<tree[tree[p].lc].num<<endl;
que=-1;
return;
}
}
if(tree[p].rc>0&&ty==1||tree[p].rc>0&&tree[p].val<que&&ty==2||tree[p].rc>0&&ty==3){
// cout<<his<<" "<<p<<" "<<tree[p].num<<" ";
his+=tree[p].num;
// cout<<his<<" "<<tree[tree[p].rc].num<<" ";
his-=tree[tree[p].rc].num;
// cout<<his<<endl;
//cout<<p<<"***"<<endl;
// if(ty==1)cout<<p<<"->"<<tree[p].rc<<" "<<endl;
dfs(tree[p].rc,ty);
}
if(tree[p].rc==0&&tree[p].val<que&&ty==2)his+=tree[p].num;
}
void query(int p,int ty){
//cout<<"((("<<tree[p].val<<endl;
if(ty==4&&tree[p].val<que){
his=p;
// cout<<"**"<<p<<" "<<que<<" "<<tree[p].val<<endl;
if(tree[p].rc>0){
query(tree[p].rc,ty);
}
return;
}
if(ty==4&&tree[p].val>=que){
if(tree[p].lc>0){
query(tree[p].lc,ty);
}
return;
}
if(ty==5&&tree[p].val<=que){
// cout<<"**"<<p<<" "<<que<<" "<<tree[p].val<<endl;
if(tree[p].rc>0){
query(tree[p].rc,ty);
}
return;
}
if(ty==5&&tree[p].val>que){
his=p;
if(tree[p].lc>0){
query(tree[p].lc,ty);
}
return;
}
}
int main(){
freopen("P3369_8.in","r",stdin);
int n;
cin>>n;
for(int i=0;i<n;i++){
int ty,x;
// cout<<"************"<<endl;
cin>>ty>>x;
// cout<<"************"<<endl;
if(ty==1)ins(x,root);
if(ty==2)del(x,root);
//dfs(root,1);
if(ty==3)que=x,his=0,dfs(root,2),cout<<his+1<<endl;
if(ty==4)que=x,dfs(root,3);
if(ty==5)que=x,his=0,query(root,4),cout<<tree[his].val<<endl;
if(ty==6)que=x,his=0,query(root,5),cout<<tree[his].val<<endl;
}
return 0;
}
//796351824-84?(3,7)
/*
100
1 914241
1 639471
5 917713
6 912745
1 234811
1 297728
3 297728
1 6927
5 645391
1 664569
2 914241
1 134689
1 868271
1 842266
5 850426
1 286545
4 1
1 333833
1 274177
1 568845
1 157569
4 13
100
1 14
1 10
1 4
1 7
1 1
1 11
2 14
1 2
1 13
1 12
1 6
1 8
1 5
1 9
1 3
4 13
100
1 914241
1 639471
1 234811
1 297728
1 6927
1 664569
1 134689
1 868271
1 842266
1 286545
1 333833
1 274177
1 568845
1 157569
4 14
*/
加载中...