[CF678F]Lena and Queries

题意：

初始有一个空集合
$n$个操作
有三种操作，如下:
$1\ a\ b$表示向集合中插入二元组$(a,b)$
$2\ i$表示删除第$i$次操作时所插入的二元组
$3\ q$表示询问当前集合的二元组中，$(a\cdot q+b)$最大是多少

先不要管插入和删除，看一看对于一堆二元组怎么样快速地处理操作3

对题目给的式子做一些微小的贡献变换，

$ans=a\cdot q+b\Rightarrow b=-a\cdot q+ans$，这等价于找（经过$(a,b)$的，斜率为$-q$的）直线，使它截距最大

脑补一下，所以我们要找的$(a,b)$一定在凸包上了

然后如果我们在凸包上找答案，答案应该是单峰的，所以不用扫，直接在凸包上三分即可

现在加上修改点集的操作

把操作1和操作2离线，处理成每个点的存在时间区间，把它放到线段树里（存在于哪些时间段就让他覆盖哪些区间，类似lazy tag）

然后再扫一遍线段树，预处理出每个线段树节点上的点集的凸包

处理询问的时候直接在线段树上经过的每个节点找最优答案，取最大值，就OK啦

总时间复杂度应该是$O(n\log^2n)$

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define inf 9223372036854775807ll
#define ll long long
struct point{
	ll x,y;
	point(int a=0,int b=0){
		x=a;
		y=b;
	}
};
point operator-(point a,point b){
	return point(a.x-b.x,a.y-b.y);
}
ll operator*(point a,point b){
	return a.x*b.y-a.y*b.x;
}
bool operator<(point a,point b){
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
typedef vector<point> vp;
vp tag[1200010];
point p[300010];
int _end[300010];
ll ask[300010];
void modify(int L,int R,int l,int r,int x){
	if(L<=l&&r<=R){
		tag[x].push_back(p[L]);
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid)modify(L,R,l,mid,x<<1);
	if(mid<R)modify(L,R,mid+1,r,x<<1|1);
}
void dfs(int l,int r,int x){
	vp&v=tag[x];
	if(!v.empty())sort(v.begin(),v.end());
	if(v.size()>2){
		int i,j;
		for(i=2,j=1;i<v.size();i++){
			while(j>0&&(v[j]-v[j-1])*(v[i]-v[j])>=0)j--;
			j++;
			v[j]=v[i];
		}
		while(v.size()>(j+1))v.pop_back();
	}
	if(l==r)return;
	int mid=(l+r)>>1;
	dfs(l,mid,x<<1);
	dfs(mid+1,r,x<<1|1);
}
ll ans;
ll calc(point p,ll v){
	return p.x*v+p.y;
}
ll solve(vp&vt,ll v){
	ll ans=-inf;
	int i,l,r,m1,m2;
	l=0;
	r=vt.size()-1;
	while(r-l>6){
		m1=(l*2+r)/3;
		m2=(l+r*2)/3;
		if(calc(vt[m1],v)<calc(vt[m2],v))
			l=m1;
		else
			r=m2;
	}
	for(i=l;i<=r;i++)ans=max(ans,calc(vt[i],v));
	return ans;
}
void query(int pos,ll v,int l,int r,int x){
	ans=max(ans,solve(tag[x],v));
	if(l==r)return;
	int mid=(l+r)>>1;
	if(pos<=mid)
		query(pos,v,l,mid,x<<1);
	else
		query(pos,v,mid+1,r,x<<1|1);
}
int main(){
	int n,i,op,x;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		_end[i]=-1;
		ask[i]=-inf;
		scanf("%d",&op);
		if(op==1){
			scanf("%I64d%I64d",&p[i].x,&p[i].y);
			_end[i]=n;
		}
		if(op==2){
			scanf("%d",&x);
			_end[x]=i-1;
		}
		if(op==3)scanf("%I64d",ask+i);
	}
	for(i=1;i<=n;i++){
		if(_end[i]!=-1)modify(i,_end[i],1,n,1);
	}
	dfs(1,n,1);
	for(i=1;i<=n;i++){
		if(ask[i]!=-inf){
			ans=-inf;
			query(i,ask[i],1,n,1);
			if(ans==-inf)
				puts("EMPTY SET");
			else
				printf("%I64d\n",ans);
		}
	}
}

巴特西

[CF678F]Lena and Queries

最新文章

热门文章