bzoj 4311: 向量 — 线段树分治+凸包

Description

Input

Output

Sample Input

Sample Output

HINT

Source

姜大爷讲完，感觉题解好巧妙

首先我们对于删除操作可以用线段树分治来实现

然后问题的怎么查询

对于一个向量的最优值，是在与该向量垂直的线中，在距离最远的线上的点的点积

所以我们可以维护出凸包，然后在凸包上三分

那么，我们第一种想法是线段树分治时合并凸包，或平衡树维护凸包？

但是这个太难了，作为蒟蒻我当然不会了qaq

所以我们可以在线段树上每一个点维护一个凸包，在查询的时候去找从根到叶子节点路径上每一个的最优值去取一个max就好啦

最后时间复杂度O(nlog²n)

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define N 200010
inline int rd()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct qaz{int x,y,l,r;}e[N],ak[N]; 
ll cj(int x,int y,int xx,int yy){return (ll)x*yy-(ll)y*xx;}
int n,tot,ta,xmn,ymn;
bool cmp(qaz a,qaz b)
{
	return cj(a.x-xmn,a.y-ymn,b.x-xmn,b.y-ymn)>0;
}
vector<int>st[N<<2],tb[N<<2];
#define ls p<<1
#define rs p<<1|1
void add(int p,int l,int r,int L,int R,int x)
{
	if(l==L&&r==R){st[p].push_back(x);return;}
	int mid=l+r>>1;
	if(R<=mid) add(ls,l,mid,L,R,x);
	else if(L>mid) add(rs,mid+1,r,L,R,x);
	else add(ls,l,mid,L,mid,x),add(rs,mid+1,r,mid+1,R,x);
}
int q[N];
bool ck(int p,int a,int b,int c)
{
	int X1,Y1,X2,Y2;
	X1=e[st[p][b]].x-e[st[p][c]].x;
	X2=e[st[p][a]].x-e[st[p][c]].x;
	Y1=e[st[p][b]].y-e[st[p][c]].y;
	Y2=e[st[p][a]].y-e[st[p][c]].y;
	return cj(X1,Y1,X2,Y2)<0;
}
void build(int p,int l,int r)
{
	if(st[p].size()<=2) tb[p]=st[p];
	else 
	{
		q[0]=0;q[1]=1;int r=1;
		st[p].push_back(st[p][0]);
		for(int i=2;i<st[p].size();i++)
		{
			while(r&&ck(p,i,q[r],q[r-1])) r--;
			q[++r]=i;
		}
		for(int i=0;i<=r;i++) tb[p].push_back(st[p][q[i]]);
	}
	if(l==r) return;
	int mid=l+r>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
ll ans;
ll Dot(qaz a,qaz b){return (ll)a.x*b.x+(ll)a.y*b.y;}
void fd(int p,int l,int r,qaz c)
{
	int L=0,R=tb[p].size()-1,m1,m2;
	while(L+3<=R)
	{
		m1=(L+L+R)/3;m2=(L+R+R)/3;
		if(Dot(e[tb[p][m1]],c)<=Dot(e[tb[p][m2]],c)) L=m1;
		else R=m2;
	}
	for(int i=L;i<=R;++i)ans=max(ans,Dot(e[tb[p][i]],c));
	if(l==r) return;
	int mid=l+r>>1;
	if(c.l<=mid) fd(ls,l,mid,c);
	else fd(rs,mid+1,r,c);
}
void ask(int x)
{
	ans=0;
	fd(1,1,n,ak[x]);
	printf("%lld\n",ans);
}
int main()
{
	n=rd();
	int x,y,op;
	for(int i=1;i<=n;i++)
	{
		op=rd();x=rd();
		if(op^2) y=rd();
		if(op==1)
		{
			e[++tot]=(qaz){x,y,i,n};
			xmn=min(x,xmn);
			ymn=min(y,ymn);
		}
		else if(op==2) e[x].r=i-1;
		else ak[++ta]=(qaz){x,y,i,0};
	}
	sort(e+1,e+tot+1,cmp);
	for(int i=1;i<=tot;i++)
		add(1,1,n,e[i].l,e[i].r,i);
	build(1,1,n);
	for(int i=1;i<=ta;i++) ask(i);
	return 0;
}