【Educational Codeforces Round 3 F】 Frogs and mosquitoes

  这道题稍微有点难度...本来想强行敲Splay的，但写C的时候逗比了没时间。然后下面大概地负数一下官方题解。

  首先按照青蛙的坐标排序，并建立一棵线段树，线段树上的每一个节点记录一只青蛙能吃到的蚊子的范围(ai,bi)，维护子树中bi的最大值。

  然后用一个multiset（注意是multiset!因为蚊子的位置可能是重叠的）记录没有被吃到的蚊子。

  对于每一只新来的蚊子，找到能吃掉它的最左边的那只青蛙（吃不掉就直接加进集合里），吃掉后青蛙这只青蛙的b变大，并在set里继续找坐标不小于原来的蚊子的蚊子，一直吃。

  关于找青蛙的操作，一种是二分青蛙的坐标x，找到那些坐标<=x的青蛙中b的最大值是否>=当前蚊子的坐标，这样的时间复杂度是O(nlog^2n)的；第二种方法是直接在线段树上找，如果左子树里最大的b>=当前蚊子坐标，则只在左子树中找，否则在右子树中找。因为如果左子树符合那个条件却找不到的话，那么右子树中是一定找不到的。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
typedef long long LL;
const int maxn=200010;

struct Frog {int x,t,id;}F[maxn];
bool cmp (const Frog &a,const Frog &b) {return a.x<b.x;}
struct Mosquito {int p,b;Mosquito(int _p,int _b):p(_p),b(_b){} bool operator< (const Mosquito &b) const {return p<b.p;}};
typedef multiset<Mosquito>::iterator Mit;
multiset <Mosquito> M;

struct Segment_Tree
{
	LL a[maxn<<2],b[maxn<<2];
	int eated[maxn<<2];
	int pos[maxn],rank[maxn];
	int n;

	#define ls (o<<1)
	#define rs ((o<<1)|1)
	#define mid ((l+r)>>1)

	void Update(int o) {b[o]=max(b[ls],b[rs]);}

	void Build(int o,int l,int r,Frog *Frogs)
	{
		if (l==r) {rank[Frogs[l].id]=o;pos[l]=o;a[o]=Frogs[l].x;b[o]=Frogs[l].t+a[o];return;}
		Build(ls,l,mid,Frogs);
		Build(rs,mid+1,r,Frogs);
		Update(o);
	}
	
	int Query(int o,int l,int r,LL x)
	{
		if (l==r) if (a[o]>x || b[o]<x) return 0;else return l;
		if (b[ls]>=x) return Query(ls,l,mid,x);
		else return Query(rs,mid+1,r,x);
	}
	
	void Change(int x,int t)
	{
		int o=pos[x];
		b[o]+=t;
		eated[o]++;
		while (o>>=1) Update(o);
	}
	
	void Print() {for (int i=1;i<=n;i++) printf("%d %I64d\n",eated[rank[i]],b[rank[i]]-a[rank[i]]);}
	int Query(int x) {return Query(1,1,n,(LL)x);}
	#undef ls
	#undef rs
	#undef mid
}T;

int n,m;

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d%d",&F[i].x,&F[i].t),F[i].id=i;
	sort(F+1,F+1+n,cmp);
	T.Build(1,1,n,F);T.n=n;
	for (int i=1,p,b;i<=m;i++)
	{
		scanf("%d%d",&p,&b);
		Mosquito temp=Mosquito(p,b);
		M.insert(temp);
		Mit eatmos=M.find(temp);
		int eatfrog;
		while (eatmos!=M.end() && (eatfrog=T.Query((*eatmos).p)))
		{
			T.Change(eatfrog,temp.b);
			M.erase(eatmos);
			eatmos=M.lower_bound(temp);
			temp=*eatmos;
		}
	}
	T.Print();
	return 0;
}