BZOJ3224 普通平衡树

解析：Splay 上裸的单点操作就好，比较好的打板题。

Source:

#include#include#include#include#include#include #include using namespace std; const int MAXN=1e6; const int INF=~0u>>1; template struct memorypool { T buf[size], *tail, *st[size]; int top; memorypool() : top(0), tail(buf) {} inline T *alloc() { return top ? st[--top] : tail++; }//* inline void recycle(T *p) { st[top++] = p; }//* }; template struct Splay { enum Relation { L=0, R=1 }; struct node { node *child[2], **root, *parent; int count, size; T value; inline void init(node *parent,node **root , const T &value) { this->parent=parent, this->root=root, this->value=value; this->count=1, child[L]=NULL, child[R]=NULL; } inline void recycle(memorypool &pool) { if(child[L]) pool.recycle(child[L]); if(child[R]) pool.recycle(child[R]); } inline Relation relation() { return this==parent->child[L] ? L : R; } inline void maintain() { size=(child[L] ? child[L]->size : 0)+(child[R] ? child[R]->size : 0)+count; } inline void rotate() { Relation x=relation(); node *oldparent = parent; if(oldparent->parent) oldparent->parent->child[oldparent->relation()]=this ; parent=oldparent->parent, oldparent->child[x]=child[x^1]; if(child[x^1]) child[x^1]->parent=oldparent; child[x^1]=oldparent, oldparent->parent=this, oldparent->maintain(),maintain(); if(!parent) *root=this; } inline void splay(node *targetparent=NULL) { while(parent!=targetparent) { if(parent->parent==targetparent) rotate(); else if(parent->relation()==relation()) parent->rotate(),rotate(); else rotate(),rotate(); } } inline node *precursor() { splay(); node *v=child[L]; while(v->child[R]) v=v->child[R]; return v; } inline node *successor() { splay(); node *v=child[R]; while(v->child[L]) v=v->child[L]; return v; } inline int rank() { return !child[L] ? 0:child[L]->size; } }*root; memorypool pool; Splay() : root(NULL) { insert(INF), insert(-INF); } inline node *find(const T &value) { node *v=root; while(v && value!=v->value) v=(value value ? v->child[L] : v->child[R]); return !v ? NULL : (v->splay(),v); } inline node *insert(const T &value) { node *v= find(value); if(v) return v->count++, v->maintain(), v; node **target=&root, *parent=NULL; while(*target) parent=*target, parent->size++, target=(value value ? &parent->child[L] : &parent->child[R]); return *target = pool.alloc(), (*target)->init(parent,&root,value ), (*target)->splay(), root; } inline void erase(const T &value) { erase(find(value)); } inline void erase(node *v) { if(v->count!=1) return v->splay(), v->count--, v->maintain(); node *precursor = v->precursor(), *successor=v->successor(); precursor->splay(), successor->splay(precursor), successor->child[L]->recycle(pool); pool.recycle(successor->child[L]) , successor->child[L]=NULL; successor->maintain(), precursor->maintain(); } inline const T &precursor(const T &value) { node *v=find(value); if(v) return v->precursor()->value; else { node *v=insert(value); const T &ans=v->precursor()->value; return erase(v), ans; } } inline const T &successor(const T &value) { node *v=find(value); if(v) return v->successor()->value; else { node *v=insert(value); const T &ans=v->successor()->value; return erase(v), ans; } } inline int rank(const T &value) { node *v=find(value); if(v) return v->rank(); else { v=insert(value); register int ans=v->rank(); return erase(v), ans; } } inline node *select(int k) { k++; node *v=root; while(!(v->rank() rank()+v->count>=k)) v=(v->rank()>=k ? v->child[L] : (k-=v->rank()+v->count, v->child[R]) ); return v->splay(), v; } }; inline void R(int &v) { char c=0; bool p=true; v=0; while(!isdigit(c)) { if(c=='-') p=false; c=getchar(); } while(isdigit(c)) { v=(v<<3)+(v<<1)+(c^'0'); c=getchar(); } if(!p) v=-v; } Splay splay; int main() { int n,type,x,ans; R(n); while(n--) { R(type),R(x); type--; switch(type) { case 0: splay.insert(x); break; case 1: splay.erase(x); break; case 3: cout< value<<'\n'; break; case 2: cout< <<'\n'; break; case 4: ans=splay.precursor(x); cout<<(ans==-INF ? -1 : ans)<<'\n'; break; case 5: ans=splay.successor(x); cout<<(ans== INF ? -1 : ans)<<'\n'; break; } } return 0; }