[HNOI2004]宠物收养场（Treap）

Treap——人和狗都收养

洛谷传送门

这题真是恶心，一开始没理解题意。

原来如果有狗，狗就会存在收养场中，直到有人来领养；

　　如果有人，人也会存在收养场中，直到有狗来被领养。

就是建一个treap，狗来把狗插进去，人来后把狗领养完，多余的人就存在treap里，等狗来。

1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 5 using namespace std; 6 7 int n, root, tot, pre, suc, flag = 1, ans; 8 int son[100001][2], size[100001], rnd[100001], w[100001]; 9 10 inline void turn(int &k, int x) 11 19 20 inline void insert(int &k, int x) 21 30 size[k]++; 31 if(w[k] < x) 32 36 else 37 41 } 42 43 inline void get_pre(int k, int x) 44 49 50 inline void get_suc(int k, int x) 51 56 57 inline void del(int &k, int x) 58 66 else 67 72 } 73 74 int main() 75 94 else flag = a, insert(root, b); 95 } 96 } 97 printf("%d", ans); 98 return 0; 99 }
View Code

上一篇：双连通分量

下一篇：[luoguP1168]中位数（主席树+离散化）

---

堆 Treap