仅有一个正整数，表示一年当中所有收养了宠物的领养者的不满意程度的总和mod1000000以后的结果。
50204131215SampleOutput3(abs(3-2)+abs(2-4)=3，最后一个领养者没有宠物可以领养)Solution用平衡树求前驱后缀
1、可以用set简单实现
#pragma__attribute__((optimize("-O2")))#include#include#include#defineoo1e9#definemo1000000#defineSTstd::settemplateinlinevoidRin(registerType&x){intc=getchar();for(x=0;c<48||c>57;c=getchar());for(;c>47&&c<58;x=(x<<1)+(x<<3)+c-48,c=getchar());}intn,ans,a,b,c,l,r;STsit;ST::iteratorit;intmain(){sit.insert(oo),sit.insert(-oo),Rin(n);for(;n;n--){Rin(a),Rin(b);if(sit.size()==2||a==c)sit.insert(b),c=a;else{it=sit.lower_bound(b),r=*it-b,l=b-*(--it);if(l<=r)(ans+=l)%=mo,sit.erase(it);else(ans+=r)%=mo,sit.erase(++it);}}printf("%d\n",ans);return0;}
