https://loj.ac/problem/10144
题目描述
宠物收养所同一时间只可能存在宠物或收养者。若收养者过多,则会选择收养者中\(|a-b|\)中最小的,若存在两个则取特征值小的那个。定义不满意度为\(\sum |a-b|\),求不满意度的总和。
思路
我们考虑由于同一时刻最多只可能有收养者或宠物,所以我们只要记录一下当前收养所内是收养者还是宠物,相同则新建节点,不相同就删除节点并累加答案。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=8e4+10;
const ll INF=0x3f3f3f3f;
const ll mod=1e6;
struct Treap
{
ll lc,rc,cnt,v,w;
}a[N];
ll root,sum;
void zig(ll &k)
{
ll t=a[k].lc;
a[k].lc=a[t].rc;
a[t].rc=k;
k=t;
}
void zag(ll &k)
{
ll t=a[k].rc;
a[k].rc=a[t].lc;
a[t].lc=k;
k=t;
}
void insert(ll &k,ll key)
{
if(!k)
{
k=++sum;
a[k].lc=a[k].rc=0;
a[k].v=key;a[k].w=rand();
a[k].cnt=1;
return ;
}
if(a[k].v==key)++a[k].cnt;
else if(a[k].v<key)
{
insert(a[k].rc,key);
if(a[a[k].rc].w<a[k].w)zag(k);
}
else
{
insert(a[k].lc,key);
if(a[a[k].lc].w<a[k].w)zig(k);
}
}
void f_delete(ll &k,ll key)
{
if(a[k].v==key)
{
if(a[k].cnt>1)--a[k].cnt;
else if(!a[k].lc||!a[k].rc)k=a[k].lc+a[k].rc;
else if(a[a[k].lc].w<a[a[k].rc].w)zig(k),f_delete(k,key);
else zag(k),f_delete(k,key);
return ;
}
if(a[k].v<key)
f_delete(a[k].rc,key);
else f_delete(a[k].lc,key);
}
ll querypre(ll key)
{
ll x=root,res=-INF;
while(x)
{
if(a[x].v<=key)res=max(res,a[x].v),x=a[x].rc;
else x=a[x].lc;
}
return res;
}
ll querynxt(ll key)
{
ll x=root,res=INF;
while(x)
{
if(a[x].v>=key)res=min(res,a[x].v),x=a[x].lc;
else x=a[x].rc;
}
return res;
}
ll read()
{
ll res=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
return res*w;
}
int main()
{
ll n=read(),tot=0;
ll ans=0,op;
while(n--)
{
ll x=read(),y=read();
if(tot==0)
{
op=x;insert(root,y);
tot=1;
continue ;
}
if(x==op)
{
insert(root,y);
tot++;
}
else
{
ll l=querypre(y),r=querynxt(y);
if(r-y<y-l)
{
f_delete(root,r);
ans=(ans+r-y)%mod;
}
else
{
f_delete(root,l);
ans=(ans+y-l)%mod;
}
tot--;
}
}
printf("%lld\n",ans);
return 0;
}