POJ-3622-Gourmet Grazers（贪心，Splay优化）

题目链接：http://poj.org/problem?id=3622

题目大意：给出n头牛，每头牛有两个属性：金钱，美味。m个产品，每个产品有两个属性：金钱，美味。只有一个产品的两个属性都大于等于牛的时候，这头牛才会去吃这个产品。问使n头牛都能吃上产品，最少花费多少。如果不能满足，输出-1；

思路：将牛的属性按照美味从大到小排列，将产品的美味从小到大排列。然后依次选牛。对于每头牛，二分出第一个可选的美味。将可选的美味都放入SplayTree中。然后从中找出最少花费的一个产品。移除SplayTree。总体复杂度O(n*log(m)*log(m))。

900+ms险过（SplayTree常数有点大）。

ACCode：

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
// srand(unsigned)time(NULL));rand();
 
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
 
#define ll long long
#define Pair pair<int,int>
#define clean(a,b) memset(a,b,sizeof(a))
using namespace std;
 
const int MAXN=1e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll MOD=1e9+7;
const double PI=acos(-1.0);
const double EPS=1.0e-8;
//unsigned register
// ios::sync_with_stdio(false)

class SplayTree{
	struct Node{
		ll A,B;
		int l,r,f,siz;
		Node(ll _A=0,ll _B=0,int _l=0,int _r=0,int _f=0,int _siz=0){
			A=_A;B=_B;l=_l;r=_r;f=_f;siz=_siz;
		}
		friend int operator < (Node a,Node b){
			if(a.A==b.A) return a.B<b.B;
			return a.A<b.A;
		}
	};
	Node Tree[MAXN];
	int Lazy[MAXN];
	int Rt,Ecnt;//Rt的父节点是0,第一个节点从1开始。  
	
	void PushUp(int x){//次序 
		Tree[x].siz=Tree[Tree[x].l].siz+Tree[Tree[x].r].siz+1;
	}
	void PushDown(int x){//反转 
		if(Lazy[x]){
			int temp=Tree[x].l;Tree[x].l=Tree[x].r;Tree[x].r=temp;
			Lazy[Tree[x].l]^=1;Lazy[Tree[x].r]^=1;
			Lazy[x]=0;
		}
	}
	void Rotate(int x,int oper){
		int y=Tree[x].f;
		PushDown(y);PushDown(x);
		if(oper){
			Tree[y].r=Tree[x].l;
			if(Tree[x].l!=0) Tree[Tree[x].l].f=y;
			Tree[x].l=y;
		}
		else{
			Tree[y].l=Tree[x].r;
			if(Tree[x].r!=0) Tree[Tree[x].r].f=y;
			Tree[x].r=y;
		}Tree[x].f=Tree[y].f;
		if(Tree[y].f){
			if(y==Tree[Tree[y].f].l) Tree[Tree[y].f].l=x;
			else Tree[Tree[y].f].r=x;
		}Tree[y].f=x;PushUp(y);
	}
	void Splay(int x,int f){
		PushDown(x);
		int y=Tree[x].f,z=0;
		while(y!=f){
			z=Tree[y].f;
			PushDown(z);PushDown(y);PushDown(x);
			if(z==f) Rotate(x,x==Tree[y].r);
			else{
				if((x==Tree[y].l^y==Tree[z].l)==0){
					Rotate(y,y==Tree[z].r);Rotate(x,x==Tree[y].r);
				}
				else{
					Rotate(x,x==Tree[y].r);Rotate(x,x==Tree[z].r);
				}
			}PushUp(x);y=Tree[x].f;
		}PushUp(x);
		if(f==0) Rt=x;
	}
	int MinNode(ll Key){
		int x=Rt,ans=-1;
		PushDown(x);
		while(1){
			if(Tree[x].A>=Key){//该节点可以取得 
				ans=x;
				if(Tree[x].l) x=Tree[x].l;//向左子节点 
				else return ans;
			}
			else{//不可以取得 
				if(Tree[x].r) x=Tree[x].r;//可以的话直接向右走了 
				else return ans;//没有符合要求的 
			}
		}
	}
	int GetPre(){
		int x=Rt;
		if(Tree[x].l) x=Tree[x].l;
		else return x;
		while(1){
			if(Tree[x].r) x=Tree[x].r;
			else return x;
		}
	}
	public:
		void Intt(){
			clean(Lazy,0);
			Rt=0;Ecnt=0;
		}
		void Insert(ll A,ll B){
			Tree[++Ecnt]=Node(A,B,0,0,0,1);
			int y=0,x=Rt;
			while(x){
				y=x;
				if(Tree[Ecnt]<Tree[x]) x=Tree[x].l;
				else if(Tree[x]<Tree[Ecnt]) x=Tree[x].r;
				else return ;
			}
			if(y==0) Rt=Ecnt;
			else if(Tree[Ecnt]<Tree[y]){
				Tree[y].l=Ecnt;Tree[Ecnt].f=y;
			}
			else{
				Tree[y].r=Ecnt;Tree[Ecnt].f=y;
			}Splay(Ecnt,0);
		}
		ll DeleteMin(ll Key){//所有的B都符合要求，找到最小的A>=P 
			int Pos=MinNode(Key);
			if(Pos==-1) return -1;
			ll Ans=Tree[Pos].A;
			Splay(Pos,0);
			//cout<<"Pos,Pre:"<<Pos<<" "<<GetPre()<<endl;
			Splay(GetPre(),0);//cout<<"Debug:\n";Show(Rt);cout<<"End\n";
			if(Pos==GetPre()){
				Rt=Tree[Rt].r;Tree[Rt].f=0;
			}
			else{
				Splay(Pos,Rt);
				Tree[Rt].r=Tree[Pos].r;Tree[Tree[Rt].r].f=Rt;	
			}
			return Ans;
		}
		//-------
		int GetRt(){
			return Rt;
		}
		void Show(int x){
			if(x==0) return ;
			PushDown(x);
			printf("x:%d xf:%d xl:%d xr:%d (A,B)(%lld,%lld)\n",x,Tree[x].f,Tree[x].l,Tree[x].r,Tree[x].A,Tree[x].B);
			Show(Tree[x].l);
//			printf("A:%lld B:%lld\n",Tree[x].A,Tree[x].B);
			Show(Tree[x].r);
		}
};
struct Node{
	ll P,G;
	Node(ll _P=0,ll _G=0){
		P=_P;G=_G;
	}
	friend int operator < (Node a,Node b){
		if(a.G==b.G) return a.P<b.P;
		return a.G<b.G;
	}
};
SplayTree Spl;
Node Cows[MAXN],Goods[MAXN];
int n,m;

int PosX(ll Key,int l,int r){
	while(l<=r){
		int mid=(l+r)>>1;
		if(Goods[mid].G<Key) l=mid+1;
		else r=mid-1;
	}return l;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%lld%lld",&Cows[i].P,&Cows[i].G);
	for(int i=1;i<=m;++i) scanf("%lld%lld",&Goods[i].P,&Goods[i].G);
	sort(Cows+1,Cows+1+n);sort(Goods+1,Goods+1+m);
	ll ans=0;int flag=1,tmp=m;
	Spl.Intt();
	for(int i=n;i>=1;--i){
		int Pos=PosX(Cows[i].G,1,tmp);
		for(int j=Pos;j<=tmp;++j) Spl.Insert(Goods[j].P,Goods[j].G);
		ll temp=Spl.DeleteMin(Cows[i].P);
		if(temp==-1){//找最小的花费 
			flag=0;break;
		}ans+=temp;tmp=Pos-1;
	}
	if(flag==0) printf("-1\n");
	else printf("%lld\n",ans);
}