蒟蒻的奇怪平衡树

排名查询有问题

删除节点用的是删除标记

这里是评测记录 QwQ

#include<iostream>
#define MAX 100011
using namespace std;
int fa[MAX],ls[MAX]={-1},rs[MAX],key[MAX],tot[MAX],size[MAX];
int lar;
bool type[MAX]={1};

inline void setp(int keyy,int faa,int lss,int rss,int sizee,int tott,bool typee,int pos){fa[pos]=faa;key[pos]=keyy;ls[pos]=lss;rs[pos]=rss;size[pos]=sizee;tot[pos]=tott;type[pos]=typee;return;}

inline void setsize(int pos){
	if(pos)
	size[pos]=size[ls[pos]]+size[rs[pos]]+tot[pos];
	else
	{
		size[pos]=0;
	 } 
}
inline void set0(int pos){
	if(pos==ls[0])type[pos]=1;
}
inline void set1(int pos1,int pos2,int pos3){
	type[pos1]=0;type[pos2]=1;type[pos3]=1;
} 

inline void set2(int pos1,int pos2,int pos3){
	int f=fa[pos1];fa[pos2]=f;
	if(pos1==ls[f])ls[f]=pos2;
	else rs[f]=pos2;
	if(pos2==ls[pos1])
	{
		int b=rs[pos2];
		if(b)fa[b]=pos1;
		pos1[ls]=b;
		rs[pos2]=pos1;
		fa[pos1]=pos2;
		}else{
		int b=ls[pos2];
		if(b)fa[b]=pos1;
		pos1[rs]=b;
		ls[pos2]=pos1;
		fa[pos1]=pos2;
	}
	setsize(pos1);
	setsize(pos3);
	setsize(pos2);
	type[pos2]=0;
	type[pos3]=1;
}

inline void set3(int pos1,int pos2,int pos3){
	int f=fa[pos1];fa[pos3]=f;
	if(pos1==ls[f])ls[f]=pos3;
	else rs[f]=pos3;//2--f
	if(pos2==ls[pos1])
	{
		int c=ls[pos3];
		int d=rs[pos3];
		fa[pos2]=pos3;
		fa[pos1]=pos3;
		ls[pos3]=pos2;
		rs[pos3]=pos1;//
		rs[pos2]=c;
		if(c)fa[c]=pos2;
		ls[pos1]=d;
		if(d)fa[d]=pos1;
	    }else{
		int c=ls[pos3];
		int d=rs[pos3];
		fa[pos2]=pos3;
		fa[pos1]=pos3;
		rs[pos3]=pos2;
		ls[pos3]=pos1;//
		ls[pos2]=d;
		if(d)fa[d]=pos2;
		rs[pos1]=c;
	    if(c)fa[c]=pos1;
	}
	setsize(pos1);
	setsize(pos2);
	setsize(pos3);
	type[pos2]=1;
	type[pos3]=0;
	type[pos1]=1;
}

inline bool ifbro(int x){
	int f=fa[x];
	return key[ls[f]]&&key[rs[f]]&&(!type[ls[f]])&&(!type[rs[f]]);
}

void pushup(int pos){//维护 
	//if(type[pos])return;
	if(!fa[pos]){type[pos]=1;return;}
	if(type[fa[pos]])//fa=1
	{//(!type[ls[fa[pos]]])&&(!type[rs[fa[pos]]])&&key[]
		if(ifbro(pos))//bro=0
		{
			set1(fa[pos],ls[fa[pos]],rs[fa[pos]]);
			pushup(fa[pos]);
		}
		return;
	}
	int pos2=fa[pos];int pos1=fa[pos2];int pos3=pos;
	if(pos2==ls[pos1])
		if(pos3==ls[pos2])		{
			set2(pos1,pos2,pos3);
			pushup(pos2);
		}
		else{
			set3(pos1,pos2,pos3);
			pushup(pos3);
		}
	else
	    if(pos3==ls[pos2]){
	    	set3(pos1,pos2,pos3);
	    	pushup(pos3);
		}
	    else{
	    	set2(pos1,pos2,pos3);
			pushup(pos2);
		}
	return;
}

void putin(int x,int pos){//插入 
	
	if(x==key[pos])
	{
		tot[pos]++;
	}
	else if(x<key[pos])
	{
		if(!ls[pos])
		{
			int a=++lar;
		    setp(x,pos,0,0,1,1,0,a);
		    ls[fa[a]]=a;
		    pushup(a);
		}
		else
		putin(x,ls[pos]);
	}
	else if(x>key[pos])
	{
		if(!rs[pos])
		{
			int a=++lar;
		    setp(x,pos,0,0,1,1,0,a);
		    rs[fa[a]]=a;
		    pushup(a);
		}else
		putin(x,rs[pos]);
	}
	setsize(pos);
}

void del(int x,int pos){//删除 
	if(x==key[pos])
	{
		if(tot[pos])
		{
			tot[pos]--;
			setsize(pos);
		}
		return;
	}
	else if(x<key[pos])
	{
		del(x,ls[pos]);
	}
	else if(x>key[pos])
	{
		del(x,rs[pos]);
	}
	setsize(pos);
}

void prt(){// 调试 
   cout<<"pos\tkey\tfa\tls\trs\ttype\ttot\tsize\n";
	for(int i=0;i<=lar;i++)
	{
		cout<<i<<":\t"<<key[i]<<"\t"<<fa[i]<<"\t"<<ls[i]<<"\t"<<rs[i]<<"\t"<<type[i]<<"\t"<<tot[i]<<"\t"<<size[i]<<"\n";
	}cout<<"\n";
}

int _kk(int x,int pos){//排名 
	int ans;
	while(key[ls[pos]]||key[rs[pos]])
	{
		if(x==key[pos])
		{
			ans+=size[ls[pos]]+1;
			return ans;
		}
		else if(x<key[pos])
		{
			pos=ls[pos];//continue;
		}
		else if(x>key[pos])
		{
			ans+=size[ls[pos]]+tot[pos];
			pos=rs[pos];//continue;
		}
	}if(x==key[pos])
		{
			ans+=size[ls[pos]]+1;
			return ans;
		}
	return 0;
}
int kk(int x,int pos){//排名 
	int ans;
	while(key[pos]!=x)
	{
		if(x<key[pos])
		{
			pos=ls[pos];//continue;
		}
		else if(x>key[pos])
		{
			ans+=size[ls[pos]]+tot[pos];
			pos=rs[pos];//continue;
		}
	}
	return ans+size[ls[pos]]+1;
}


int xx(int k,int pos){//数值 
	while(key[ls[pos]]||key[rs[pos]])
	{
		if(k<=size[ls[pos]])
		{
			pos=ls[pos];
		}
		else if(k>size[ls[pos]]&&k<=size[ls[pos]]+tot[pos])
		{
			return key[pos];
		}
		else if(k>size[ls[pos]]+tot[pos])
		{
			k-=(size[ls[pos]]+tot[pos]);
			pos=rs[pos];
		}
	}
	if(k>size[ls[pos]]&&k<=size[ls[pos]]+tot[pos])
		{
			return key[pos];
		}
		return 0;
}

int bfer(int x,int pos){// 前驱
	int ans=0;
	while(key[pos])
	{
		if(key[pos]<x)
		{
			ans=pos;pos=rs[pos];
		}
		else
		{
			pos=ls[pos];
		}
	}
	if(tot[ans])
	return key[ans];
	else
	return bfer(key[ans],rs[0]);
}

int afer(int x,int pos){// 后驱
	int ans=0;
	while(key[pos])
	{
		if(key[pos]>x)
		{
			ans=pos;pos=ls[pos];
		 } 
		else
		{
			pos=rs[pos];
		}
	} 
	if(tot[ans])
	return key[ans];
	else
	return afer(key[ans],rs[0]);
}


void work()
{
	int t;
	cin>>t;
	int x;
	for(int i=0;i<t;i++)
	{
		int opt;
		cin>>opt>>x;
		switch(opt)
		{
			case 1:{
				putin(x,0);
			//	prt();
			break;}
			case 2:{
				del(x,0);
			//	prt();
			break;}
			case 3:{
				cout<<kk(x,rs[0])<<"\n";
			break;}
			case 4:{
				cout<<xx(x,rs[0])<<"\n";
			break;}
			case 5:{
			    cout<<bfer(x,rs[0])<<"\n";
			break;} 
			case 6:{
				cout<<afer(x,rs[0])<<"\n";
				
			break;}
			case 7:{
				return;
			}
		}
	}
}

int main()
{
//	freopen("P3369_5.in","r",stdin);
//	freopen("qqqq.out","w",stdout);
	work();
	return 0;
}