这道题比上一道稍微复杂那么一些……不过大体上还是很容易的！
没有必要建立两棵splay，一棵就够了。我们可以记录一下当前在收养场的情况，如果cnt>0说明宠物多，否则人多，然后挨个判断即可。
如果宠物多还来宠物就直接插入，人也同理。
反之，如果宠物多了之后来人了，那就在这堆宠物中找其对应值的前驱后继，答案加上小的那个就可以了。然后把那个值删除。反之同理。
看一下代码。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<cstring> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') #define pr pair<int,int> #define mp make_pair #define fi first #define sc second using namespace std; typedef long long ll; const int M = 100005; const int mod = 1000000; const int INF = 1000000009; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >='0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct node { int ch[2],cnt,son,fa,val; }t[M<<1]; int n,a,b,root,idx,tot,cur; bool get(int x) { return t[t[x].fa].ch[1] == x; } void pushup(int x) { t[x].son = t[t[x].ch[0]].son + t[t[x].ch[1]].son + t[x].cnt; } void rotate(int x) { int y = t[x].fa,z = t[y].fa,k = get(x); t[z].ch[t[z].ch[1] == y] = x,t[x].fa = z; t[y].ch[k] = t[x].ch[k^1],t[t[y].ch[k]].fa = y; t[x].ch[k^1] = y,t[y].fa = x; pushup(x),pushup(y); } void splay(int x,int goal) { while(t[x].fa != goal) { int y = t[x].fa,z = t[y].fa; if(z != goal) (t[y].ch[1] == x) ^ (t[z].ch[1] == y) ? rotate(x) : rotate(y); rotate(x); } if(goal == 0) root = x; } void insert(int x) { int u = root,f = 0; while(u && x != t[u].val) f = u,u = t[u].ch[x > t[u].val]; if(u) t[u].cnt++; else { u = ++idx; if(f) t[f].ch[x > t[f].val] = u; t[u].ch[0] = t[u].ch[1] = 0; t[u].fa = f,t[u].son = t[u].cnt = 1,t[u].val = x; } splay(u,0); } void find(int x) { int u = root; if(!u) return; while(t[u].ch[x > t[u].val] && x != t[u].val) u = t[u].ch[x > t[u].val]; splay(u,0); } int next(int x,int f) { find(x); int u = root; if(t[u].val > x && f) return u; if(t[u].val < x && !f) return u; u = t[u].ch[f]; while(t[u].ch[f^1]) u = t[u].ch[f^1]; return u; } void del(int x) { int p = next(x,0),q = next(x,1); splay(p,0),splay(q,p); int g = t[q].ch[0]; if(t[g].cnt > 1) t[g].cnt--; else t[q].ch[0] = 0; } int main() { n = read(); insert(INF),insert(-INF); rep(i,1,n) { a = read(),b = read(); if(a == 0 && cur >= 0) cur++,insert(b); else if(a == 1 && cur <= 0) cur--,insert(b); else if(a == 0 && cur < 0) { int a1 = t[next(b,0)].val,a2 = t[next(b,1)].val; if(abs(a1-b) <= abs(a2-b)) tot += abs(a1-b),tot %= mod,del(a1); else tot += abs(a2-b),tot %= mod,del(a2); cur++; } else if(a == 1 && cur > 0) { int a1 = t[next(b,0)].val,a2 = t[next(b,1)].val; if(abs(a1-b) <= abs(a2-b)) tot += abs(a1-b),tot %= mod,del(a1); else tot += abs(a2-b),tot %= mod,del(a2); cur--; } } printf("%d ",tot % mod); return 0; }