洛谷传送门
这题真是恶心，一开始没理解题意。
原来如果有狗，狗就会存在收养场中，直到有人来领养；
如果有人，人也会存在收养场中，直到有狗来被领养。
就是建一个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
上一篇：【模板】划分树
下一篇：飞行员配对方案问题（匈牙利算法+sort）
Treap 堆
