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;
}
顺便,只是顺便评价一下马蜂