【set】【Splay】【pb_ds】bzoj1208 [HNOI2004]宠物收养所

每次来的如果是人，且宠物数不为零，就从宠物中选出一个与其差距最小的，累加答案；若为零，就把他放入另一个集合里。

如果是宠物，则同上。

各种平衡树都可过，我蛋疼地用了pb_ds。

Code:

 #include<cstdio>

 #include<ext/pb_ds/assoc_container.hpp>

 #include<ext/pb_ds/tree_policy.hpp>

 using namespace std;

 using namespace __gnu_cxx;

 using namespace __gnu_pbds;

 tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> T[];

 typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>::iterator ITER;

 int n,op,a,ans;

 inline bool empty(const int &x){return T[x].lower_bound(-)==T[x].end() ? true : false;}

 inline int Abs(const int &x){return x< ? (-x) : x;}

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

       {

           scanf("%d%d",&op,&a);

           if(empty(op^))

             T[op].insert(a);

           else

             {

                 ITER it=T[op^].lower_bound(a);

                 if((*it)==a)

                   T[op^].erase(it);

                 else

                   {

                       ITER it2=T[op^].upper_bound(a);

                       if(it==T[op^].begin())

                         {

                             ans=(ans+Abs(a-(*it2)))%;

                             T[op^].erase(it2);

                             continue;

                         }

                       it--;

                       if(it2==T[op^].end())

                         {

                             ans=(ans+Abs(a-(*it)))%;

                             T[op^].erase(it);

                             continue;

                         }

                       if(Abs(a-(*it2))<Abs(a-(*it)))

                         {

                             ans=(ans+Abs(a-(*it2)))%;

                             T[op^].erase(it2);

                             continue;

                         }

                       else

                         {

                             ans=(ans+Abs(a-(*it)))%;

                             T[op^].erase(it);

                         }

                   }

             }

       }

     printf("%d\n",ans);

     return ;

 }