【BZOJ4311】向量（线段树分治，斜率优化）

题面

BZOJ

题解

先考虑对于给定的向量集，如何求解和当前向量的最大内积。

设当前向量\((x,y)\)，有两个不同的向量\((u1,v1),(u2,v2)\)，并且\(u1>u2\)

假设第一个向量的结果优于第二个。

\(xu1+yv1>xu2+yv2\)

移项可以得到

\(x(u1-u2)>y(v2-v1)\)

所以\(x/y>(v2-v1)/(u1-u2)\)

也就是\(-x/y>(v1-v2)/(u1-u2)\)

右边是一个斜率，左边是询问向量和原点构成的斜率的垂线。

所以维护一个上凸壳，每次在上面二分（三分）一下就好了

时间复杂度\(O(nlog^2n)\)

按照之前听到的方法，因为每次询问如果排序之后，二分的结果是单调的，

所以暴力扫一遍就好。时间复杂度\(O(nlogn)\)

我写的是两个log的。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define lson (now<<1)

#define rson (now<<1|1)

#define MAX 200200

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=true,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return t?-x:x;

}

struct Vector{int x,y,l,r;}p[MAX],q[MAX];

bool cmp(Vector a,Vector b)

{

	if(a.x!=b.x)return a.x<b.x;

	return a.y<b.y;

}

int tot,Tim,n;

ll ans[MAX];

vector<Vector> seg[MAX<<2];

void Modify(int now,int l,int r,int L,int R,int id)

{

	if(L<=l&&r<=R){seg[now].push_back(p[id]);return;}

	int mid=(l+r)>>1;

	if(L<=mid)Modify(lson,l,mid,L,R,id);

	if(R>mid)Modify(rson,mid+1,r,L,R,id);

}

ll inner(Vector a,Vector b){return 1ll*a.x*b.x+1ll*a.y*b.y;}

ll Cross(Vector a,Vector b,Vector c){return 1ll*(a.x-c.x)*(b.y-c.y)-1ll*(a.y-c.y)*(b.x-c.x);}

Vector S[MAX];

int Top;

ll Query(int id)

{

	int l=1,r=Top;ll ret=0;

	while(l+3<=r)

	{

		int mid1=l+(r-l)/3,mid2=r-(r-l)/3;

		if(inner(q[id],S[mid1])<=inner(q[id],S[mid2]))l=mid1;

		else r=mid2;

	}

	for(int i=l;i<=r;++i)ret=max(ret,inner(q[id],S[i]));

	return ret;

}

void Work(int now,int l,int r)

{

	if(!seg[now].size())return;Top=0;

	sort(seg[now].begin(),seg[now].end(),cmp);

	for(int i=0,len=seg[now].size();i<len;++i)

	{

		Vector u=seg[now][i];

		while(Top>1&&Cross(S[Top-1],S[Top],u)>=0)--Top;

		S[++Top]=seg[now][i];

	}

	for(int i=l;i<=r;++i)ans[i]=max(ans[i],Query(i));

	if(l==r)return;int mid=(l+r)>>1;

}

void Divide(int now,int l,int r)

{

	Work(now,l,r);

	if(l==r)return;int mid=(l+r)>>1;

	Divide(lson,l,mid);Divide(rson,mid+1,r);

}

int main()

{

	n=read();

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

	{

		int opt=read();

		if(opt==1)

		{

			int x=read(),y=read();

			p[++tot]=(Vector){x,y,Tim+1,-1};

		}

		else if(opt==2)

			p[read()].r=Tim;

		else

		{

			int x=read(),y=read();

			q[++Tim]=(Vector){x,y,Tim,Tim};

		}

	}

	for(int i=1;i<=tot;++i)if(p[i].r==-1)p[i].r=Tim;

	for(int i=1;i<=tot;++i)if(p[i].l<=p[i].r)Modify(1,1,Tim,p[i].l,p[i].r,i);

	Divide(1,1,Tim);

	for(int i=1;i<=Tim;++i)printf("%lld\n",ans[i]);

	return 0;

}