这题真是恶心，一开始没理解题意。
原来如果有狗，狗就会存在收养场中，直到有人来领养；
如果有人，人也会存在收养场中，直到有狗来被领养。
就是建一个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 { 12 int t = son[k][x]; 13 son[k][x] = son[t][x ^ 1]; 14 son[t][x ^ 1] = k; 15 size[t] = size[k]; 16 size[k] = size[son[k][0]] + size[son[k][1]] + 1; 17 k = t; 18 } 19 20 inline void insert(int &k, int x) 21 { 22 if(!k) 23 { 24 k = ++tot; 25 w[k] = x; 26 rnd[k] = rand(); 27 size[k] = 1; 28 return; 29 } 30 size[k]++; 31 if(w[k] < x) 32 { 33 insert(son[k][1], x); 34 if(rnd[k] > rnd[son[k][1]]) turn(k, 1); 35 } 36 else 37 { 38 insert(son[k][0], x); 39 if(rnd[k] > rnd[son[k][0]]) turn(k, 0); 40 } 41 } 42 43 inline void get_pre(int k, int x) 44 { 45 if(!k) return; 46 if(w[k] > x) get_pre(son[k][0], x); 47 else pre = k, get_pre(son[k][1], x); 48 } 49 50 inline void get_suc(int k, int x) 51 { 52 if(!k) return; 53 if(w[k] < x) get_suc(son[k][1], x); 54 else suc = k, get_suc(son[k][0], x); 55 } 56 57 inline void del(int &k, int x) 58 { 59 if(!k) return; 60 if(w[k] == x) 61 { 62 if(son[k][0] * son[k][1] == 0) k = son[k][0] + son[k][1]; 63 else if(rnd[son[k][0]] < rnd[son[k][1]]) turn(k, 0), del(k, x); 64 else turn(k, 1), del(k, x); 65 } 66 else 67 { 68 size[k]--; 69 if(w[k] > x) del(son[k][0], x); 70 else del(son[k][1], x); 71 } 72 } 73 74 int main() 75 { 76 int i, a, b, x; 77 scanf("%d", &n); 78 for(i = 1; i <= n; i++) 79 { 80 scanf("%d %d", &a, &b); 81 if(flag == a) insert(root, b); 82 else 83 { 84 if(size[root]) 85 { 86 pre = 0, get_pre(root, b); 87 suc = 0, get_suc(root, b); 88 if(!pre || !suc) x = pre + suc; 89 else if(b - w[pre] <= w[suc] - b) x = pre; 90 else x = suc; 91 ans = (ans + abs(w[x] - b)) % 1000000; 92 del(root, w[x]); 93 } 94 else flag = a, insert(root, b); 95 } 96 } 97 printf("%d", ans); 98 return 0; 99 }