【贪心】【二维偏序】【权值分块】bzoj1691 [Usaco2007 Dec]挑剔的美食家

既然题目中的要求满足二维偏序，那么我们很自然地想到将所有东西(草和牛)都读进来之后，对一维(美味度)排序，然后在另一维(价值)中取当前最小的。

于是，Splay、mutiset、权值分块什么的都支持查询后继呢。

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int Num,CH[],f,c;

 inline void R(int &x){

     c=;f=;

     for(;c<''||c>'';c=getchar())if(c=='-')f=-;

     for(x=;c>=''&&c<='';c=getchar())(x*=)+=(c-'');

     x*=f;

 }

 long long ans;

 struct Val3{int c,v;bool is;void Read(){R(c);R(v);}}a[];

 struct Point{int v,p;}t[];

 bool operator < (const Val3 &a,const Val3 &b){return a.v!=b.v ? a.v>b.v : a.is>b.is;}

 bool operator < (const Point &a,const Point &b){return a.v<b.v;}

 int n,m,en,ma[],b[],sumv[],l[],r[],num[],sum=;

 int B[];

 void makeblock()

 {

     int sz=sqrt(en); if(!sz) sz=;

     for(;sum*sz<en;++sum)

       {

           l[sum]=r[sum-]+; r[sum]=sum*sz;

           for(int i=l[sum];i<=r[sum];++i) num[i]=sum;

       }

     l[sum]=r[sum-]+; r[sum]=en;

     for(int i=l[sum];i<=r[sum];++i) num[i]=sum;

 }

 void Insert(const int &x){++B[x]; ++sumv[num[x]];}

 void Delete(const int &x){--B[x]; --sumv[num[x]];}

 int Next(const int &x)

 {

     for(int i=x;i<=r[num[x]];i++) if(B[i]) return i;

     for(int i=num[x]+;i<=sum;i++) if(sumv[i])

       for(int j=l[i];j<=r[i];j++)

         if(B[j]) return j;

     return -;

 }

 int main()

 {

     R(n); R(m);

     for(int i=;i<=n;++i) a[i].Read();

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

       {

           a[i].Read();

           a[i].is=;

       }

     sort(a+,a+n+m+);

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

       {

           t[i].v=a[i].c;

           t[i].p=i;

       }

     sort(t+,t++n+m);

     ma[b[t[].p]=++en]=t[].v;

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

       {

         if(t[i].v!=t[i-].v) ++en;

         ma[b[t[i].p]=en]=t[i].v;

       } makeblock();

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

       if(a[i].is) Insert(b[i]);

       else

         {

           int Nex=Next(b[i]);

           if(Nex==-)

             {

               puts("-1");

               return ;

             }

           ans+=(long long)ma[Nex];

           Delete(Nex);

         }

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

     return ;

 }