首页分享 AcWing 1281. 宠物收养所+Treap

AcWing 1281. 宠物收养所+Treap

来源：萌宠菠菠乐园时间：2025-04-24 23:12

题目描述

最近，阿 Q 开了一间宠物收养所。

收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。

每个领养者都希望领养到自己满意的宠物，阿 Q 根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值 a（a 是一个正整数，a<231），而他也给每个处在收养所的宠物一个特点值，这样他就能够很方便的处理整个领养宠物的过程了。

宠物收养所总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。

被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为 a，那么它将会领养一只目前未被领养的宠物中特点值最接近 a 的一只宠物。任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的。如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为 a−b 和 a+b，那么领养者将会领养特点值为 a−b 的那只宠物；
收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为 a，存在两个领养者他们希望领养宠物的特点值分别为 a−b 和 a+b，那么特点值为 a−b 的那个领养者将成功领养该宠物。一个领养者领养了一个特点值为 a 的宠物，而它本身希望领养的宠物的特点值为 b，那么这个领养者的不满意程度为 |a−b|。
你得到了一年当中，领养者和被收养宠物到来收养所的情况，希望你计算所有收养了宠物的领养者的不满意程度的总和。

这一年初始时，收养所里面既没有宠物，也没有领养者。

输入格式
第一行为一个正整数 n，表示一年当中来到收养所的宠物和领养者的总数；

接下来的 n 行，按到来时间的先后顺序描述了一年当中来到收养所的宠物和领养者的情况。每行有两个正整数 a,b，其中 a=0 表示宠物，a=1 表示领养者，b 表示宠物的特点值或是领养者希望领养宠物的特点值。

同一时间呆在收养所中的，要么全是宠物，要么全是领养者，这些宠物和领养者的个数不会超过 104 个。

输出格式
仅有一个正整数，表示一年当中所有收养了宠物的领养者的不满意程度的总和对 106 取模以后的结果。

数据范围
1≤n≤8×104

样例

输入样例：
5
0 2
0 4
1 3
1 2
1 5
输出样例：
3
样例解释
|3−2|+|2−4|=3，最后一个领养者没有宠物可以领养。

treap

思路：看到找最接近的并且动态修改就想到平衡树
建两颗平衡树，tr1表示人，tr2表示宠物，每次插入对应的树，然后找前驱和后驱，如果是无穷说明没有，否则就删除
操作：插入，删除，前驱，后驱
易错点：两份平衡树代码毫不相关，不要彼此出现在对方的代码中

C++ 代码

#include<bits/stdc++.h> using namespace std; #define int long long const int N=80005,INF=0x3f3f3f3f,mod=1e6; typedef long long LL; struct node{ int l,r; int key,val,cnt; }tr1[N]; struct Node{ int l,r; int key,val,cnt; }tr2[N]; int root1,idx1; int root2,idx2; int n,sz1,sz2; int get_node1(int key){ tr1[++idx1].key=key; tr1[idx1].val=rand(); tr1[idx1].cnt=1; return idx1; } void zig1(int &p){//右旋 int q=tr1[p].l; tr1[p].l=tr1[q].r,tr1[q].r=p,p=q; } void zag1(int &p){//左旋 int q=tr1[p].r; tr1[p].r=tr1[q].l,tr1[q].l=p,p=q; } void build1(){ get_node1(-INF),get_node1(INF); root1=1,tr1[1].r=2; if(tr1[2].val>tr1[1].val) zag1(root1); } int get_node2(int key){ tr2[++idx2].key=key; tr2[idx2].val=rand(); tr2[idx2].cnt=1; return idx2; } void zig2(int &p){//右旋 int q=tr2[p].l; tr2[p].l=tr2[q].r,tr2[q].r=p,p=q; } void zag2(int &p){//左旋 int q=tr2[p].r; tr2[p].r=tr2[q].l,tr2[q].l=p,p=q; } void build2(){ get_node2(-INF),get_node2(INF); root2=1,tr2[1].r=2; if(tr2[2].val>tr2[1].val) zag2(root2); } void insert1(int &p,int key){ if(!p) p=get_node1(key); else if(tr1[p].key==key) tr1[p].cnt++; else if(tr1[p].key>key){ insert1(tr1[p].l,key); if(tr1[tr1[p].l].val>tr1[p].val) zig1(p); } else{ insert1(tr1[p].r,key); if(tr1[tr1[p].r].val>tr1[p].val) zag1(p); } } void remove1(int &p,int key){ if(!p) return; if(tr1[p].key==key){ if(tr1[p].cnt>1) tr1[p].cnt--; else if(tr1[p].l||tr1[p].r){ if(!tr1[p].r||tr1[tr1[p].l].val>tr1[tr1[p].r].val){ zig1(p); remove1(tr1[p].r,key);; } else{ zag1(p); remove1(tr1[p].l,key);; } } else p=0; } else if(tr1[p].key>key) remove1(tr1[p].l,key); else remove1(tr1[p].r,key); } int get_prev1(int p,int key){ if(!p) return -INF; if(tr1[p].key>=key) return get_prev1(tr1[p].l,key); return max(tr1[p].key,get_prev1(tr1[p].r,key)); } int get_next1(int p,int key){ if(!p) return INF; if(tr1[p].key<=key) return get_next1(tr1[p].r,key); return min(tr1[p].key,get_next1(tr1[p].l,key)); } void insert2(int &p,int key){ if(!p) p=get_node2(key); else if(tr2[p].key==key) tr2[p].cnt++; else if(tr2[p].key>key){ insert2(tr2[p].l,key); if(tr2[tr2[p].l].val>tr2[p].val) zig2(p); } else{ insert2(tr2[p].r,key); if(tr2[tr2[p].r].val>tr2[p].val) zag2(p); } } void remove2(int &p,int key){ if(!p) return; if(tr2[p].key==key){ if(tr2[p].cnt>1) tr2[p].cnt--; else if(tr2[p].l||tr2[p].r){ if(!tr2[p].r||tr2[tr2[p].l].val>tr2[tr2[p].r].val){ zig2(p); remove2(tr2[p].r,key);; } else{ zag2(p); remove2(tr2[p].l,key); } } else p=0; } else if(tr2[p].key>key) remove2(tr2[p].l,key); else remove2(tr2[p].r,key); } int get_prev2(int p,int key){ if(!p) return -INF; if(tr2[p].key>=key) return get_prev2(tr2[p].l,key); return max(tr2[p].key,get_prev2(tr2[p].r,key)); } int get_next2(int p,int key){ if(!p) return INF; if(tr2[p].key<=key) return get_next2(tr2[p].r,key); return min(tr2[p].key,get_next2(tr2[p].l,key)); } signed main(){ ios::sync_with_stdio(false); cin>>n; LL res=0; build1(),build2(); for(int i=1;i<=n;i++){ int op,k; cin>>op>>k; if(op==1){ insert1(root1,k); int temp1=get_prev2(root2,k),temp2=get_next2(root2,k); if(temp1==-INF&&temp2==INF) continue; if(temp1==temp2||abs(temp1-k)<abs(temp2-k)){ res=(res+abs(temp1-k))%mod; remove2(root2,temp1); remove1(root1,k); } else{ res=(res+abs(temp2-k))%mod; remove2(root2,temp2); remove1(root1,k); } } else{ insert2(root2,k); int temp1=get_prev1(root1,k),temp2=get_next1(root1,k); if(temp1==-INF&&temp2==INF) continue; if(temp1==temp2||abs(temp1-k)<abs(temp2-k)){ res=(res+abs(temp1-k))%mod; remove1(root1,temp1); remove2(root2,k); } else{ res=(res+abs(temp2-k))%mod; remove1(root1,temp2); remove2(root2,k); } } } cout<<res%mod<<endl; return 0; }