自动搬运

查看原文

来自洛谷，原作者为

	qwaszx 不再为往事受困.

搬运于2025-08-24 21:47:35，当前版本为作者最后更新于2019-06-27 10:30:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不失一般性设当前询问的$y_0>0$，那么$\dfrac{ans}{y_0}=\max\{\dfrac{x_0}{y_0}\cdot x+y\}$，然后这个东西和斜率优化长得一样，答案一定是在凸壳上的.

于是我们维护这个凸壳.因为有区间询问所以线段树维护每个区间的凸壳.具体地，插入的时候统计当前区间已经有多少个点，如果点数等于当前区间长度那么构造出这个区间的凸壳.询问的时候拆成$\log$个区间分别跑二分/三分即可.

求凸包这里使用按$x$坐标排序的那个算法.注意如果几个点的$x$相同那么要按$y$排序.

插入的时候每个区间只会被构建一次凸包，总复杂度$O(n\log n)$，排序用归并.

查询的时候拆成$\log$个区间，每个区间$O(\log n)$三分/二分，总复杂度$O(n\log ^2 n)$

使用$vector$可以很方便地在每个节点开一个栈，但是非常吃氧(不开$O2$会T最后一个点).可以不用$stl$，用一个大栈存下所有区间的凸包，对每个线段树节点存下它所在凸包的起止点即可.

这里当然还是用无脑的$vector$了233

这道题还告诉我们所有长成$f[i]=\min\limits_{L(i)\leq j\leq R(i)}\{k(i)x(j)+F(j)\}+G(i)$的$dp$都是可做的233

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N=2e6;
long long lastans;
struct Point{
	int x,y;
	bool operator <(const Point &a)const{return x!=a.x?x<a.x:y<a.y;}
	Point operator -(const Point &a)const{return (Point){x-a.x,y-a.y};}
	long long operator *(const Point &a)const{return 1ll*x*a.y-1ll*y*a.x;}
};
struct Node{vector<Point>st[2];}a[N];
int size[N],n;
char st[5];
long long calc(int rot,int x,int y)
{
	int o=0;
	if(y<0)x=-x,y=-y,o=1;
	int l=0,r=a[rot].st[o].size()-1;
//	cout<<rot<<" "<<l<<" "<<r<<endl;
	while(l<r)
	{
		int mid=(l+r)>>1;//cout<<l<<" "<<r<<" "<<mid<<endl;
		if(-1ll*x*(a[rot].st[o][mid+1].x-a[rot].st[o][mid].x)>=1ll*y*(a[rot].st[o][mid+1].y-a[rot].st[o][mid].y))r=mid;
		else l=mid+1;
	}
//	cout<<l<<endl;
	return 1ll*x*a[rot].st[o][l].x+1ll*y*a[rot].st[o][l].y;
}
long long query(int rot,int lt,int rt,int lq,int rq,int x,int y)
{
	if(lt>=lq&&rt<=rq)return calc(rot,x,y);
	int mid=(lt+rt)>>1;
	if(rq<=mid)return query(rot<<1,lt,mid,lq,rq,x,y);
	else if(lq>mid)return query(rot<<1|1,mid+1,rt,lq,rq,x,y);
	else return max(query(rot<<1,lt,mid,lq,mid,x,y),query(rot<<1|1,mid+1,rt,mid+1,rq,x,y));
}
void build(int rot,int len)
{
	for(int o=0;o<=1;o++)
	{
		vector<Point>tmp;tmp.clear();
		vector<Point>::iterator i=a[rot<<1].st[o].begin(),j=a[rot<<1|1].st[o].begin();
		for(;i!=a[rot<<1].st[o].end()||j!=a[rot<<1|1].st[o].end();)
			if(i==a[rot<<1].st[o].end()||(j!=a[rot<<1|1].st[o].end()&&*j<*i))tmp.push_back(*j++);
			else tmp.push_back(*i++);
		int top=0;
		for(vector<Point>::iterator i=tmp.begin();i!=tmp.end();++i)
		{
			while(top>1&&((a[rot].st[o][top-1]-a[rot].st[o][top-2])*(*i-a[rot].st[o][top-1]))>=0)--top,a[rot].st[o].pop_back();
			a[rot].st[o].push_back(*i);++top;
		}
	}
}
void update(int rot,int lt,int rt,int q,int x,int y)
{
	if(lt==rt){a[rot].st[0].push_back((Point){x,y}),a[rot].st[1].push_back((Point){-x,-y}),++size[rot];return;}
	int mid=(lt+rt)>>1;
	if(q<=mid)update(rot<<1,lt,mid,q,x,y);
	else update(rot<<1|1,mid+1,rt,q,x,y);
	++size[rot];if(size[rot]==rt-lt+1)build(rot,rt-lt+1);
}
void deco(int &x)
{
	x^=(lastans&0x7fffffff);
}
void print(int rot,int lt,int rt)
{
	printf("%d %d %d\n",rot,lt,rt);
	int mid=(lt+rt)>>1;
	if(lt!=rt)print(rot<<1,lt,mid),print(rot<<1|1,mid+1,rt);
}
int main()
{
	int enc=0;
	scanf("%d%s",&n,st+1);if(st[1]!='E')enc=1;
//	cout<<enc<<endl;
//	freopen("cswa.txt","w",stdout);
	int nn=0;//print(1,1,n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",st+1);
		if(st[1]=='Q')
		{
			int l,r,x,y;
			scanf("%d%d%d%d",&x,&y,&l,&r);
			if(enc)deco(x),deco(y),deco(l),deco(r);
//			cout<<x<<" "<<y<<" "<<l<<" "<<r<<endl;
			printf("%lld\n",lastans=query(1,1,n,l,r,x,y));
		}
		else
		{
			int x,y;
			scanf("%d%d",&x,&y);
			if(enc)deco(x),deco(y);
//			cout<<x<<" "<<y<<endl;
			update(1,1,n,++nn,x,y);
		}
//		print(1,1,n);
	}
}