我又双叒叕来求助了
查看原帖
我又双叒叕来求助了
13805
Ackoter楼主2020/7/28 10:11

2~4点随机RE,5~10点RE,其他AC,求查错

#define k1 (a->v<v) 
#define k2 (a->son[0]->fix<a->son[1]->fix)
using namespace std;
int n,type,sum;
struct P{
	int v,lj,fix;
	int siz;//×ÓÊ÷´óС 
	P *son[2];
	P(int _v=0):v(_v), lj(1), son{NULL,NULL}, fix(rand()) ,siz(1)
	{
	}
	void tj()
	{
		siz=lj;
		if(son[0]!=NULL) siz+=son[0]->siz;
		if(son[1]!=NULL) siz+=son[1]->siz;
	}
}no,*sw;
P finds(P *a,int v)
{
	if(a==NULL) return no;
	if(a->v==v) return *a;
	return finds(a->son[(a->v)<v],v);
}
void xuan(P *&f,int er)
{
	sw=f->son[er^1];
	f->son[er^1]=sw->son[er],sw->son[er]=f;
	f->tj(),f=sw,f->tj();
}
void updata(P *&a,int v)
{
	if(a==NULL) {a=new P(v);return;}
	if(a->v==v) a->lj++;
	updata(a->son[k1],v);
	a->tj();
	if(a->son[k1]->fix<a->fix) xuan(a,k1^1);
}
void Delete(P *&a,int v)
{
	if(a==NULL) return;
	if(a->v==v)
	{
		if(a->lj>1) {a->lj--;a->tj();return;}
		if(a->son[1]==NULL) a=a->son[0]; else
			if(a->son[0]==NULL) a=a->son[1]; else
				xuan(a,k2),Delete(a->son[k2],v),a->tj();
		return;
	}
	Delete(a->son[k1],v),a->tj(); 
}
P finds_m(P *a,int type)
{
	if(a==NULL) return 2147483647*(1-type*2);
	while(a->son[type]) a=a->son[type];
	return *a;
}
int Rank(P *a,int v)
{
	if(a==NULL) return 0;
	if(!k1) return Rank(a->son[0],v);
	int ls=a->son[0] ? a->son[0]->siz : 0;
	return ls+a->lj+Rank(a->son[1],v);
}
P RankFinds(P *a,int x)
{
	int ls=a->son[0] ? a->son[0]->siz:0;
	if(x>=ls+1&&x<=ls+a->lj) return a->v;
	return RankFinds(a->son[x>ls+a->lj],x-(x>ls+a->lj ? ls+a->lj : 0));
}
int Getqu(P *a,int x,int type)
{
	if(a==NULL) return 2147483647;
	if((a->v-x)*(1-type*2)>=0) return Getqu(a->son[type],x,type);
	int tmp=Getqu(a->son[type^1],x,type);
	if(tmp!=2147483647) return tmp; else return a->v;
}
int main()
{
	srand(time(0));
	scanf("%d",&n);
	P fi;
	fi.fix=fi.v=-2100000000;
	P *r=&fi;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&type,&sum);
		if(type==1) updata(r,sum); else
			if(type==2) Delete(r,sum); else
				if(type==3) printf("%d\n",Rank(&fi,sum)); else
					if(type==4) printf("%d\n",RankFinds(&fi,sum+1).v); else
						if(type==5) printf("%d\n",Getqu(&fi,sum,0)); else
							printf("%d\n",Getqu(&fi,sum,1));
	}
	return 0;
}

顺便,只是顺便评价一下马蜂

2020/7/28 10:11
加载中...