(据说codevs要更新就不放codevs的地址了吧...)
有宠物和人,每个单位都有一个与其他单位不同的值(正),如果现在有宠物,来了一个人,人取走和他的值最接近的宠物(如果有两个选值小的),如果现在有人,来了一个宠物,和它值最接近的人(如果有两个选值小的)取走它.求每次带宠物走两个单位的值的差的绝对值的总和.
仅有一个正整数，表示一年当中所有收养了宠物的领养者的不满意程度的总和mod1000000以后的结果。
用平衡树查找前驱和后驱即可.依照题意,要么全是人要么全是宠物,所以建一棵树即可.模板题.
注意:
1.判断是否有前驱或后驱时要小心.
p.s.第一道用Splay写的题,调了好久...指针理解的不是很好啊.
Treap:
set:
1#include2usingnamespacestd;34constintmod=1000000;5intn,ans,a,b,now,cnt;6setst;7intmain(){8scanf("%d",&n);9set::iteratorit;10while(n--){11scanf("%d%d",&a,&b);12if(!cnt)now=a;13if(a==now)st.insert(b),cnt++;14else{15it=st.lower_bound(b);16if(it!=st.end()&&it!=st.begin()){17intsuc=*it,pre=*(--it);18if(b-pre<=suc-b){19st.erase(pre);20ans=(ans+b-pre)%mod;21}22else{23st.erase(suc);24ans=(ans+suc-b)%mod;25}26}27elseif(it!=st.end()){28intsuc=*it;29st.erase(suc);30ans=(ans+suc-b)%mod;31}32else{33intpre=*(--it);34st.erase(pre);35ans=(ans+b-pre)%mod;36}37cnt--;38}39}40printf("%d\n",ans);41return0;42}
