hdu 5127（cdq分治+凸包）

参考了这篇博客 http://blog.csdn.net/u013912596/article/details/47978791 

我的做法：

其实每次询问就是 找一个向量(x,y)使得 （x,y)*(p,q)最大。根据向量点积的性质很容易发现最优的向量肯定在凸包上。

如果没有删除操作，可以用平衡树来维护上凸壳和下凸壳，每次询问二分查找。

这题有删除操作，看了题解再想了很久才知道怎么分治。

对于一个操作区间【L,R】：

如果【L,mid】区间内的添加的向量在 R 之后被删除或者不删，那么就可以用它们构建上下凸壳来更新【mid+1,R】区间内的询问。

如果【mid+1，R】区间内的删除的向量在 L 之前添加，那么也可以用它们构建上下凸壳来更新【L,mid】区间内的询问。

然后就做完了。

一些小技巧：下凸壳可以翻转一下变成上凸壳用同样的方法维护，nxt数组记录与操作i相关的另一个操作的位置，可以很方便的判断它是添加操作还是删除操作。

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=50005;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n;
ll ans[N];
int nxt[N];
struct P
{
	int x,y;
	bool operator<(const P &t)const
	{
		return x<t.x||x==t.x&&y>t.y;
	}
	P operator-(const P &t)
	{
		return {x-t.x,y-t.y};
	}
	ll operator*(const P &t)
	{
		return 1ll*x*t.x+1ll*y*t.y;
	}
	ll operator^(const P &t)
	{
		return 1ll*x*t.y-1ll*y*t.x;
	}
}a[N];
ll cross(P a,P b,P c)
{
	return (b-a)^(c-b);
}
map<P,int>mp;
struct hull
{
	int n,top;
	P a[N],stk[N];
	void init()
	{
		n=0;
	}
	void add(P p)
	{
		a[++n]=p;
	}
	void make()
	{
		sort(a+1,a+n+1);
		top=0;
		for (int i=1;i<=n;i++)
		{
			while(top>1&&cross(stk[top-1],stk[top],a[i])>=0) top--;
			stk[++top]=a[i];
		}
	}
	ll get(P p)
	{
		if (top==0) return -INF;
		int l=1,r=top;
		while(l<r)
		{
			int mid=(l+r)/2;
			if (p*stk[mid]<p*stk[mid+1]) l=mid+1;else r=mid;
		}
		return p*stk[l];
	}
}up,down;
void solve(int l,int r)
{
	if (l==r) return;
	int mid=(l+r)/2;

	up.init(); down.init();
	for (int i=l;i<=mid;i++)
		if (nxt[i]>r)
		{
			up.add(a[i]);
			down.add({a[i].x,-a[i].y});
		}
	up.make(); down.make();
	for (int i=mid+1;i<=r;i++)
		if (nxt[i]==i)
		{
			ans[i]=max(ans[i],up.get(a[i])),
			ans[i]=max(ans[i],down.get({a[i].x,-a[i].y}));
		}

	up.init(); down.init();
	for (int i=mid+1;i<=r;i++)
		if (nxt[i]<l)
		{
			up.add(a[i]);
			down.add({a[i].x,-a[i].y});
		}
	up.make(); down.make();
	for (int i=l;i<=mid;i++)
		if (nxt[i]==i)
		{
			ans[i]=max(ans[i],up.get(a[i]));
			ans[i]=max(ans[i],down.get({a[i].x,-a[i].y}));
		}

	solve(l,mid);
	solve(mid+1,r);
}
int main()
{
	while(scanf("%d",&n),n)
	{
		mp.clear();
		for (int i=1;i<=n;i++) ans[i]=-INF;
		for (int i=1;i<=n;i++)
		{
			int tp;
			scanf("%d%d%d",&tp,&a[i].x,&a[i].y);
			if (tp==1) nxt[i]=n+1,mp[a[i]]=i;
			if (tp==-1)
			{
				int id=mp[a[i]];
				nxt[id]=i; nxt[i]=id;
				mp.erase(a[i]);
			}
			if (tp==0) nxt[i]=i;
		}
		solve(1,n);
		for (int i=1;i<=n;i++)
			if (nxt[i]==i) printf("%lld\n",ans[i]);
	}
}