寫平衡樹修鍋快修到死系列
我太蠢了
其實是平衡樹裸體裸題
插入，刪除，交換前驅或后繼，查詢rank和kth
維護一個pos數組，表示第i個書的編號
然后注意許許多多的細節，沒了
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct Node{int lson,rson,ran,val,w,sz;
}Treap[80000<<2];
int pos[80100],Lx,Rx,Nodecnt,n,m,root;
void pushup(int o){Treap[o].sz=Treap[Treap[o].lson].sz+Treap[Treap[o].rson].sz+1;
}
void rotateR(int &o){int k=Treap[o].lson;Treap[o].lson=Treap[k].rson;Treap[k].rson=o;Treap[k].sz=Treap[o].sz;pushup(o);o=k;
}
void rotateL(int &o){int k=Treap[o].rson;Treap[o].rson=Treap[k].lson;Treap[k].lson=o;Treap[k].sz=Treap[o].sz;pushup(o);o=k;
}
int NewNode(int cx,int wl){++Nodecnt;Treap[Nodecnt].sz=1;Treap[Nodecnt].lson=Treap[Nodecnt].rson=0;Treap[Nodecnt].ran=rand();Treap[Nodecnt].val=wl;Treap[Nodecnt].w=cx;return Nodecnt;
}
void insert(int &o,int cx,int wl){if(!o){o=NewNode(cx,wl);return;}Treap[o].sz++;if(wl<=Treap[o].val){insert(Treap[o].lson,cx,wl);if(Treap[Treap[o].lson].ran<Treap[o].ran)rotateR(o);// pushup(o);}else{insert(Treap[o].rson,cx,wl);if(Treap[Treap[o].rson].ran<Treap[o].ran)rotateL(o);// pushup(o);}
}
void erase(int &o,int wl){if(!o)return;if(Treap[o].val==wl){if(Treap[o].lson==0||Treap[o].rson==0){o=Treap[o].lson+Treap[o].rson;return;}if(Treap[Treap[o].lson].ran<Treap[Treap[o].rson].ran){rotateR(o);erase(o,wl);}else{rotateL(o);erase(o,wl);}pushup(o);return;}Treap[o].sz--;if(wl<=Treap[o].val){erase(Treap[o].lson,wl);pushup(o);}else{erase(Treap[o].rson,wl);pushup(o);}
}
int ranks(int o,int wl){if(!o)return 0;if(wl==Treap[o].val){return Treap[Treap[o].lson].sz+1;}if(wl<=Treap[o].val){return ranks(Treap[o].lson,wl);} else{return ranks(Treap[o].rson,wl)+Treap[Treap[o].lson].sz+1;}
}
int kth(int k,int o){if(k==0)return 0;if(k==Treap[Treap[o].lson].sz+1)return Treap[o].w;if(k<=Treap[Treap[o].lson].sz)return kth(k,Treap[o].lson);elsereturn kth(k-Treap[Treap[o].lson].sz-1,Treap[o].rson);
}
int pre(int wl){return kth(ranks(root,wl)-1,root);
}
int back(int wl){return kth(ranks(root,wl)+1,root);
}
int main(){Lx=1;// freopen("7.in","r",stdin);// freopen("test.out","w",stdout);srand(19260817);scanf("%d %d",&n,&m);for(int i=1;i<=n;i++){int x;scanf("%d",&x);++Rx;pos[x]=Rx;insert(root,x,Rx);}char opt[20];int sx,tx;for(int i=1;i<=m;i++){scanf("%s",opt);if(opt[0]=='T'){scanf("%d",&sx);erase(root,pos[sx]);Lx--;pos[sx]=Lx;insert(root,sx,Lx);}else if(opt[0]=='B'){scanf("%d",&sx);erase(root,pos[sx]);Rx++;pos[sx]=Rx;insert(root,sx,Rx);}else if(opt[0]=='I'){scanf("%d %d",&sx,&tx);if(tx==0)continue;if(tx==1){int need=back(pos[sx]);erase(root,pos[sx]);erase(root,pos[need]);swap(pos[sx],pos[need]);insert(root,sx,pos[sx]);insert(root,need,pos[need]); }if(tx==-1){int need=pre(pos[sx]);erase(root,pos[sx]);erase(root,pos[need]);swap(pos[sx],pos[need]);insert(root,sx,pos[sx]);insert(root,need,pos[need]);}}else if(opt[0]=='A'){scanf("%d",&sx);printf("%d\n",ranks(root,pos[sx])-1);}else if(opt[0]=='Q'){scanf("%d",&sx);printf("%d\n",kth(sx,root));}}return 0;
}
轉載于:https://www.cnblogs.com/dreagonm/p/10029180.html
總結
以上是生活随笔為你收集整理的p2596 书架（Treap）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
