题目链接：https://loj.ac/problem/10144#submit_code
解题思路
Treap模板题，肯定会只剩宠物或者只剩领养动物的，所以只用开一个树就行。之后用模板就行。
AC代码
#include <iostream> #include <stdio.h> #include <algorithm> using namespace std; typedef long long ll; // 1代表宠物 2代表人 int cnt1, cnt2; int tot; int rt; int n, a; ll b; const int N = 8e4 + 5; const ll inf = (1 << 33); const ll mod = 1e6; struct node { int lc, rc, p; ll v; #define lc(x) t[x].lc #define rc(x) t[x].rc #define v(x) t[x].v #define p(x) t[x].p } t[N]; inline void Zig(int &k) //右旋,这里加了个引用&,目的是更加方便地处理父子关系 { int y = lc(k); //选取当前结点k的左子结点 lc(k) = rc(y); rc(y) = k; //交换y,k的父子位置,并维持BST性质 k = y; } inline void Zag(int &k) //左旋 { int y = rc(k); //选取当前结点k的右子结点 rc(k) = lc(y); lc(y) = k; //交换y,k的父子位置,并维持BST性质 k = y; } inline void insert(int &k, const ll val) //插入结点 { if (!k) { k = ++tot; v(k) = val; p(k) = rand(); // p(k)为随机的优先级 lc(k) = rc(k) = 0; return; } if (val < v(k)) { insert(lc(k), val); if (p(lc(k)) < p(k)) //维护Treap堆性质 Zig(k); } else { insert(rc(k), val); if (p(rc(k)) < p(k)) Zag(k); //维护Treap堆性质 } return; } inline void Delete(int &k, const ll val) { if (v(k) == val) { if (!lc(k) || !rc(k)) //链结点可以直接删 k = lc(k) + rc(k); else if (p(lc(k)) < p(rc(k))) Zig(k), Delete(k, val); else Zag(k), Delete(k, val); return; } if (val < v(k)) Delete(lc(k), val); else Delete(rc(k), val); return; } inline ll QueryPre(const ll val) //求一个元素在Treap中的前驱 { int x = rt, res = -inf; while (x) { if (v(x) <= val) //要求的前驱为结点x或在结点x的右子树内 res = v(x), x = rc(x); else x = lc(x); } return res; } inline ll QuerySuf(const ll val) //求一个元素在Treap中的后继 { int x = rt, res = inf; while (x) { if (v(x) >= val) //要求的前驱为结点x或在结点x的左子树内 res = v(x), x = lc(x); else x = rc(x); } return res; } int main() { scanf("%d", &n); ll ans = 0; while (n--) { scanf("%d%lld", &a, &b); if (!a) { if (!cnt2) { insert(rt, b); cnt1++; } else { cnt2--; ll tmp1 = QueryPre(b); ll tmp2 = QuerySuf(b); if (tmp1 == -inf) { ans += tmp2 - b; Delete(rt, tmp2); } else if (tmp2 == inf) { ans += b - tmp1; Delete(rt, tmp1); } else if (b - tmp1 <= tmp2 - b) { ans += b - tmp1; Delete(rt, tmp1); } else { ans += tmp2 - b; Delete(rt, tmp2); } ans %= mod; } // cout<<"ans "<<ans<<endl; } else { if (!cnt1) { insert(rt, b); cnt2++; } else { cnt1--; ll tmp1 = QueryPre(b); ll tmp2 = QuerySuf(b); if (tmp1 == -inf) { ans += tmp2 - b; Delete(rt, tmp2); } else if (tmp2 == inf) { ans += b - tmp1; Delete(rt, tmp1); } else if (b - tmp1 <= tmp2 - b) { ans += b - tmp1; Delete(rt, tmp1); } else { ans += tmp2 - b; Delete(rt, tmp2); } ans %= mod; } // cout<<"ans "<<ans<<endl; } } printf("%lldn", ans); return 0; }
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152
