最近两天在搞平衡树,搞得自己都恶心了,两页的提交记录红绿相间。
蒟蒻突然不想数组转指针了,但写都写了,不调出来,怪不舒服的。。。。。。。求助大佬
#include<cstdio>
#include<cstdlib>
#define INF 0x7fffffff
using namespace std;
const int N=1e5+10;
struct Treap{
Treap *ch[2];
int dat,val,cnt,siz;
Treap(int v):dat=rand(),val=v,cnt=siz=1,ch[0]=ch[1]=NULL{}
int cmp(int x)const{
if(x==val) return -1;
return x>val;
}
up(){
siz=cnt;
if(ch[0]!=NULL) siz+=ch[0]->siz;
if(ch[1]!=NULL) siz+=ch[1]->siz;
}
};
// Treap *null=new Treap();
Treap* root;
void rotate(Treap* &o,int d){
Treap* k=o->ch[d^1];
o->ch[d^1]=k->ch[d];
k->ch[d]=o;
o=k;
o->ch[d]->up();
o->up();
}
void insert(Treap* &o,int x){
if(o==NULL) o=new Treap(x);
else{
int d=o->cmp(x);
if(d==-1){a[o].cnt++,o->up();return;}
insert(o->ch[d],x);o->up();
if(o->ch[d]->dat>o->dat) rotate(o,d^1);
}
}
void remove(Treap* &o,int x){
if(o==NULL) return;
int d=o->cmp(x);
if(d==-1){
if(o->cnt>1){o->cnt--,o->up();return;}
if(o->ch[0]==NULL) o=o->ch[1];
else if(o->ch[1]==NULL) o=o->ch[0];
else{
int d2=o->ch[0]->dat>a->o->ch[1]->dat;
rotate(o,d2);remove(o->ch[d2],x);
}
}
else remove(o->ch[d],x);
up(o);
}
int getpre(Treap* o,int val){
Treap* ans;
while(o!=NULL){
if(o->val>=val) o=o->ch[0];
else ans=o,o=o->ch[1];
}
return ans->val;
}
int getsuc(Treap* o,int val){
Treap* ans;
while(o!=NULL){
if(o->val<=val) o=o->ch[1];
else ans=o,o=o->ch[0];
}
return ans->val;
}
int getk(Treap* o,int rank){
if(o->ch[0]->siz>=rank) return getk(o->ch[0],rank);
if(o->cnt+o->ch[0]->siz>=rank) return a[o].val;
return getk(o->ch[1],rank-o->cnt-o->ch[0]->cnt);
}
int getkth(Treap* o,int val){
if(val==o->val) return o->ch[0]->siz+1;
if(val<o->val) return getkth(o->ch[0],val);
return getkth(o->ch[1],val)+o->cnt+o->ch[0]->siz;
}
int n,opt,x;
int main(){
scanf("%d",&n);
while(n--){
scanf("%d%d",&opt,&x);
switch(opt){
case 1:insert(root,x);break;
case 2:remove(root,x);break;
case 3:printf("%d\n",getkth(root,x));break;
case 4:printf("%d\n",getk(root,x));break;
case 5:printf("%d\n",getpre(root,x));break;
case 6:printf("%d\n",getpre(root,x));break;
}
}
}