|算法討論|平衡樹學習筆記

2019-11-14 11:26:17

字體：大中小

來源：轉載

供稿：網友

平衡樹：Treap，Splay，Set

Treap，Splay實現名次樹：BZOJ 3224 普通平衡樹

#include<cstdio> #include<algorithm> #include<cstring> #include<vector> #define ms(i,j) memset(i,j, sizeof i); using namespace std; struct node{ node *ch[2];//左右孩子 int v, r;//值，優先級 int s;//附加值：以當前節點為根的結點數量 int w;//附加值：和當前節點相同值的結點數 void mt() { s = w; if (ch[0]!=NULL) s += ch[0]->s; if (ch[1]!=NULL) s += ch[1]->s; } };int ans;struct treap{ node *root; void rotate(int d, node *&o)//d=0則左旋 d=1則右旋 { node *k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o; o->mt(); k->mt(); o = k; } void insert(int x, node *&o)//插入一個數 { if (o==NULL) { o = new node(); o->v = x; o->r = rand(); o->s = o->w = 1; o->ch[0] = o->ch[1] = NULL; //初值 } else if (o->v==x) o->w++; //有相同直接w++ else { int d = (x < o->v ? 0 : 1); insert(x, o->ch[d]); if (o->ch[d]->r > o->r) rotate(d^1, o); } o->mt(); } void del(int x, node *&o)//刪除一個數 { int d = (x < o->v ? 0 : 1); if (o->v==x)//找到 { if (o->w>1) {o->w--; o->s--;} else//不止一個數就直接w--，s-- 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]->r > o->ch[1]->r ? 1 : 0); rotate(d2,o); del(x, o->ch[d2]); } } else { del(x, o->ch[d]); } if (o!=NULL) o->mt(); } int rank(int x, node *o)//求x的排名 { int tmp; if (o->ch[0]==NULL) tmp = 0; else tmp=o->ch[0]->s;//求s if (o->v==x) return tmp+1;//找到了 else if (o->v >x) return rank(x,o->ch[0]); else return tmp+o->w+rank(x,o->ch[1]); } int kth(int k, node *o)//求第k小 { if (o==NULL||o->s<k||k<=0) return -1;//不符合要求 int tmp; if (o->ch[0]==NULL) tmp = 0; else tmp = o->ch[0]->s;//求s if (k<=tmp) return kth(k,o->ch[0]); else if (k > tmp+o->w) return kth(k - tmp - o->w,o->ch[1]); else return o->v;//找到了 } void PRed(int x, node *o)//求前驅 { if(o==NULL)return; if(o->v<x) { ans = o->v; pred(x, o->ch[1]); } else pred(x, o->ch[0]); } void succ(int x, node *o)//求后繼 { if(o==NULL)return; if(o->v>x) { ans = o->v; succ(x, o->ch[0]); } else succ(x, o->ch[1]); }};treap tree;int n;int main() { scanf("%d", &n); int opt,x; for (int i=1;i<=n;i++) { scanf("%d%d", &opt, &x); switch(opt) { case 1: tree.insert(x, tree.root); break; case 2: tree.del(x, tree.root); break; case 3: printf("%d/n", tree.rank(x, tree.root)); break; case 4: printf("%d/n", tree.kth(x, tree.root)); break; case 5: tree.pred(x,tree.root); printf("%d/n", ans); break; case 6: tree.succ(x,tree.root); printf("%d/n", ans); break; } } return 0; }

Set求大于x的最小值：BZOJ 2028[SHOI2009]會場預約

#include<cstdio> #include<algorithm> #include<cstring> #include<set> #define ms(i,j) memset(i,j, sizeof i); using namespace std; int n; struct qj { int l, r; bool Operator <(const qj &b) const { if (r<b.r) return true; if (r>b.r) return false; return l<b.l; }};set<qj> s; char inpu(){ char ans = getchar(); while ((ans!='A')&&(ans!='B')) ans = getchar(); return ans;}int main() { scanf("%d", &n); for (int i=1;i<=n;i++) { char type = inpu(); if (type=='A') { int cnt = 0; int l,r; scanf("%d%d", &l, &r); qj a = (qj){l,r}; while (true) { set<qj>::iterator it = s.lower_bound((qj){0,l});//找第一個比a大的qj int xl = it->l, xr = it->r; if (it!=s.end())//set里還有元素 { if (!(a.r < it->l))//有覆蓋 { s.erase(it); cnt++; continue; } } s.insert(a); break; } printf("%d/n", cnt); } else printf("%d/n", s.size()); } return 0; }

上一篇：springMVC簡單學習

下一篇：Linux下安裝JDK