我们还是可以使用上一题的思路： STL:set营业统计额

就是继续用$set$的自动排序和lower_bound功能，只是多了一种情况和一些细节：

情况

本题有两种情况，一种是宠物等着人来领养，另一种是人等着领养宠物，我们可以用一个$cnt$来区分两种情况

每当$set<int>s$中没有了数，新来的那一个如果是宠物，那就是第一种情况，此时$cnt=0$

如果新来的是人就是第二种情况，此时$cnt=1$

往后只要$set<int>s$中还有数，那如果新来的$op=cnt$，那就是直接加入，$op!=cnt$就是要进行计算了

细节

计算的情况与 “营业统计额” 一样，但要加上一前一后两个哨兵，因为宠物被领养或人领养宠物离开后，对应的数需要删去，没有这两个哨兵容易越界，知道这一点即可......

#include<bits/stdc++.h>
using namespace std;
set<int>s;
int main()
{
	int n,ans=0,cnt;scanf("%d",&n);
	s.insert(INT_MIN);s.insert(INT_MAX);
	for(int i=1,x,op;i<=n;i++)
	{
		scanf("%d%d",&op,&x);
		if(s.size()==2)cnt=op,s.insert(x);
		else if(op==cnt)s.insert(x);
		else
		{
			auto bi=s.lower_bound(x),sm=--s.lower_bound(x);
			if((x-*sm)<=(*bi-x)&*sm!=INT_MIN)
				ans+=x-*sm,s.erase(*sm);
			else ans+=*bi-x,s.erase(*bi);
			ans%=1000000;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

set解法

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000;
int main()
{
    int n;scanf("%d",&n);
    int ans=0;
    set<int>S[2];
    for(int i=1;i<=n;i++)
    {
        int t,x;scanf("%d%d",&t,&x);
        if(S[t^1].empty()){S[t].insert(x);continue;}

        if(x>*(--S[t^1].end()))
        {
            ans+=x-*(--S[t^1].end());ans%=mod;
            S[t^1].erase(*(--S[t^1].end()));
        }
        else if(x<*(S[t^1].begin()))
        {
            ans+=*(S[t^1].begin())-x;ans%=mod;
            S[t^1].erase(*(S[t^1].begin()));
        }
        else
        {
            auto it=S[t^1].lower_bound(x);
            int nxt=*it,pre=*(--it);
            if(x-pre<=next-x)S[t^1].erase(pre),ans=(ans+x-pre)%mod;
            else S[t^1].erase(nxt),ans=(ans+nxt-x)%mod;
        }
    }
    printf("%d\n",ans);
    return 0;
}

splay解法

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000,inf=0x3f3f3f3f;
struct trnode{int d,c,n,f,ch[2];}tr[110000];int len,root;
void upd(int x){tr[x].c=tr[tr[x].ch[0]].c+tr[tr[x].ch[1]].c+tr[x].n;}
void add(int d,int f)
{
	tr[++len]=trnode{d,1,1,f,0,0};
	tr[f].ch[tr[f].d<d]=len;
	if(f==0)root=len;
}
void rotate(int x)
{
	int y=tr[x].f,z=tr[y].f,w=(tr[y].ch[1]==x),v=tr[x].ch[1-w];
	tr[y].ch[w]             =v;tr[v].f=y;
	tr[x].ch[1-w]           =y;tr[y].f=x;
	tr[z].ch[tr[z].ch[1]==y]=x;tr[x].f=z;
	upd(y);upd(x);
}
void splay(int x,int rt)
{
	while(tr[x].f!=rt) {
		int y=tr[x].f,z=tr[y].f;
		if(rt!=z)((tr[y].ch[1]==x)==(tr[z].ch[1]==y))?rotate(y):rotate(x);
		rotate(x);
	}
	if(rt==0)root=x;
}
int findip(int d)
{
	int x=root;
	while(tr[x].d!=d&&tr[x].ch[tr[x].d<d])x=tr[x].ch[tr[x].d<d];
	return x;
}
int findnext(int d,int w)
{
	int x=findip(d);
	if(tr[x].d>d&&w==1)return x;
	if(tr[x].d<d&&w==0)return x;
	splay(x,0);x=tr[x].ch[w];
	while(tr[x].ch[1-w])x=tr[x].ch[1-w];
	return x;
}
void ins(int d)
{
	if(root==0)add(d,0);
	else {
		int x=findip(d);
		if(tr[x].d==d)tr[x].n++,splay(x,0);
		else           add(d,x),splay(len,0);
	}
}
void del(int d)
{
	int qq=findnext(d,0),hj=findnext(d,1);
	splay(qq,0);splay(hj,qq);
	int x=tr[hj].ch[0];
	if(tr[x].n>1)tr[x].n--,splay(x,0);
	else tr[hj].ch[0]=0,splay(hj,0);
}
int main()
{
	int n;scanf("%d",&n);
	len=root=0;ins(-inf);ins(inf);
	int flag=-1,ans=0;;
	for(int i=1;i<=n;i++)
	{
		int c,x;scanf("%d%d",&c,&x);
		if(flag==c)ins(x);
		else if(flag==-1){flag=c;ins(x);}
		else {
			int p=findip(x);
			if(tr[p].d==x)del(x);
			else {
				int q=findnext(x,0),h=findnext(x,1);
				if( tr[q].d!=-inf && tr[h].d!=inf) {
					if(x-tr[q].d<=tr[h].d-x)ans+=x-tr[q].d,del(tr[q].d);
					else                    ans+=tr[h].d-x,del(tr[h].d);
				}
				else if(tr[q].d==-inf)      ans+=tr[h].d-x,del(tr[h].d);
				else if(tr[h].d==inf)       ans+=x-tr[q].d,del(tr[q].d);
			}
			if(tr[root].c==2)flag=-1;
		}
		ans=ans%mod;
	}
	printf("%d\n",ans);
	return 0;
}