RBST (AOJ 1508 RMQ)
RBSTの実装をした.
struct RBSTとするとよくわからんバグが起こるし,カプセル化する意味も特にないと思ったのでグローバルにした.
struct node{ //node of RBST int val,mn,size; node *lch,*rch; node(int v){ val=mn=v; size=1; lch=0,rch=0; } }; typedef pair<node*,node*> Pnn; node *root; //すべての関数は操作した後の木の親のポインタを返す node *update(node *x){ x->size=1; x->mn=x->val; if(x->lch){ x->size+=x->lch->size; chmin(x->mn,x->lch->mn); } if(x->rch){ x->size+=x->rch->size; chmin(x->mn,x->rch->mn); } return x; } node *merge(node *x,node *y){ if(x==0) return y; if(y==0) return x; int m=x->size,n=y->size; if(xor128()%(m+n)<m){ x->rch=merge(x->rch,y); return update(x); }else{ y->lch=merge(x,y->lch); return update(y); } } int count(node *x){ if(x==0) return 0; return x->size; } Pnn split(node *x,int pos){ //[,pos),[pos,) if(x==0) return Pnn(0,0); if(pos<=count(x->lch)){ Pnn tmp=split(x->lch,pos); x->lch=tmp.sc; return Pnn(tmp.fs,update(x)); }else{ Pnn tmp=split(x->rch,pos-count(x->lch)-1); x->rch=tmp.fs; return Pnn(update(x),tmp.sc); } } node *insert(node *x,int pos,int val){ node *p = new node(val); Pnn tmp=split(x,pos); node *l=merge(tmp.fs,p),*r=tmp.sc; return merge(l,r); } node *erase(node *x,int pos){ Pnn tmp=split(x,pos); node *l=tmp.fs,*r=split(tmp.sc,1).sc; return merge(l,r); } void showtree(node *c){ if(!c) return; cout<<"("; showtree(c->lch); cout<<""<< c->val <<""; showtree(c->rch); cout<<")"; } void query0(int b,int c){ Pnn x=split(root,c); Pnn y=split(x.fs,b); Pnn z=split(x.sc,1); // show(count(z.sc)); node *t=merge(y.fs,z.fs); node *s=merge(y.sc,z.sc); // showtree(t);puts(""); // showtree(s);puts(""); root=merge(t,s); } void query1(int b,int c){ Pnn x=split(root,b); Pnn y=split(x.sc,c+1-b); // show(count(y.fs)); cout<<y.fs->mn<<endl; root=merge(x.fs,merge(y.fs,y.sc)); } void query2(int b,int c){ root=erase(root,b); root=insert(root,b,c); }
update:
中核.これがよばれたら(その部分は)正しい値(例えば区間のminとか)を持つことが保証される.
merge,split:
再帰的に行っていて,再帰の終わりにupdateをつけておくことでこれらが呼ばれた後(その部分は)正しいものが帰ってくることが保証される.
insert,erase:
返り値を持っていて,殆どの場合x=insert(x,pos,val)みたいな感じになる(voidにしてもいいかもしれないが,もしかしてこの形じゃないものもあるかもしれないので,なれておく)
showtree:
便利.nodeの情報が多い場合shownodeを作ってもよさそう.
呼ぶ側(query):
この問題では
query0:[l,r]の区間を右にひとつずらす(a[r]は場所lに行く).
query1:min a[l~r]を答える
query2:a[i]をxにする
の3種類.
何個かに分割した後は適当にmergeした後それをroot(もしくはsubtreeのroot)に設定する.
y=split(x,pos)みたいなことをした後xは使わない方がいい.
次は永続化かなあ.