一个领养者领养了一个特点值为a的宠物，而它本身希望领养的宠物的特点值为b，那么这个领养者的不满意程度为abs(a-b)。
【任务描述】你得到了一年当中，领养者和被收养宠物到来收养所的情况，希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。
仅有一个正整数，表示一年当中所有收养了宠物的领养者的不满意程度的总和mod1000000以后的结果。
splay模板题··当然用set做更简单···，按照题意往splay树种加入人或宠物的特殊值，按照题意加入后要么树种全是宠物或人的特殊值，此时直接继续加入操作；要么有一个人的特殊值剩下的全是宠物，或者有一个宠物的特殊值剩下的全是人，因此直接按照题意删除一个人和一个宠物（即一次领养）即可；注意用cnt1和cnt0来记录人和宠物在树中的数量
1.splay
#include#include#include#include#include#include#include#include#include#includeusingnamespacestd;constintN=8e4+5;constintmod=1000000;constintinf=1e+9;setst;intn,cnt0=0,cnt1=0,a,b;longlongans=0;inlineintR(){charc;intf=0;for(c=getchar();c<'0'||c>'9';c=getchar());for(;c<='9'&&c>='0';c=getchar())f=(f<<3)+(f<<1)+c-'0';returnf;}longlongAbs(longlongx){returnx<0-x:x;}intmain(){//freopen("a.in","r",stdin);n=R();st.insert(-inf);st.insert(inf);for(inti=1;i<=n;i++){a=R(),b=R();if(!cnt0&&!cnt1){if(a==0)cnt0++;elsecnt1++;st.insert(b);}elseif(!cnt0&&a==1){cnt1++;st.insert(b);}elseif(!cnt1&&a==0){cnt0++;st.insert(b);}else{if(!cnt1)cnt0--;elseif(!cnt0)cnt1--;set::iteratorl=--st.lower_bound(b),r=st.lower_bound(b);if(b-*l<=*r-b&&*l!=-inf){ans+=b-*l;st.erase(l);}else{ans+=*r-b;st.erase(r);}ans%=mod;}}printf("%d",ans);return0;}
