luogu P4756 Added Sequence（凸包+思维）

一眼望去不会。
考虑问题中的\(f(i,j)=|\sum_{p=i}^{j}?a_p? |\)的实际意义。
其实就是前缀和相减的绝对值。
\(f(i,j)=|\ sum[j]-sum[i-1]\ |\)
\(f(i,j)=max(sum[j]-sum[i-1],sum[i-1]-sum[j])\)
那加上x呢。
\(f(i,j)=max[(sum[j]+xj)-(sum[i-1]+x(i-1)),(sum[i-1]+x(i-1))-(sum[j]+xj)]\)
\(sum[i]+xi\)联想到直线。
我们把这些直线放到坐标系里。
(这个图是从别人那里蒯过来的)

这是把样例转为坐标系中直线的效果图。
对于一个 \(x\) ，我们询问的实际上就是横坐标为x的两条直线纵坐标的差的最大值。
所以我们用半平面交的方法维护出上下两个凸包。
因为题目中的强制在线是假的（实际上处理出的\(x\in [-2n,2n]\)）。
又因为凸包上的线段斜率是单调的，我们可以直接处理出所有 \(x\) 时的答案。
然后这题就解决了。

#include
#include
#include
#include
#include
#include
using namespace std;
const int N=201000;
const double eps=1e-8;
double sum[N];
struct node{
	double x,y;
	node(double xx=0,double yy=0){
		x=xx;y=yy;
	}
};
int top1,top2;
struct Line{
	node u,v;
	double w;
}a[N],stack1[N],stack2[N];
node operator +(node a,node b){
	return node(a.x+b.x,a.y+b.y);
}
node operator -(node a,node b){
	return node(a.x-b.x,a.y-b.y);
}
node operator *(node a,double b){
	return node(a.x*b,a.y*b);
}
double chaji(node a,node b){
	return a.x*b.y-a.y*b.x;
}
node jiao(Line a,Line b){
	double A=chaji(b.u-a.u,b.v-a.u);
	double B=chaji(b.v-a.v,b.u-a.v);
	return a.u+(a.v-a.u)*(A/(A+B));
}
bool judge1(Line a,Line b,Line c){
	node x=jiao(b,c);
	if(chaji(x-a.u,a.v-a.u)+eps>=0)return true;
	else return false;
}
bool judge2(Line a,Line b,Line c){
	node x=jiao(b,c);
	if(chaji(x-a.u,a.v-a.u)+eps<0)return true;
	else return false;
}
int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return sum*f;
}
int n,m;
double w(Line a,double x){
//	cout<ans;
long long lastans;
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++)sum[i]=sum[i-1]+read();
	for(int i=1;i<=n;i++){
		a[i].u=node(-2.0*n,sum[i]+i*-2.0*n);
		a[i].v=node(2.0*n,sum[i]+i*2.0*n);
		a[i].w=i;
	}
	a[0].u=node(-2.0*n,0);a[0].v=node(2.0*n,0);
	a[0].w=0;
	for(int i=0;i<=n;i++){
		while(top1>1&&judge1(a[i],stack1[top1-1],stack1[top1]))top1--;
		stack1[++top1]=a[i];
	}
	for(int i=n;i>=0;i--){
		while(top2>1&&judge2(a[i],stack2[top2-1],stack2[top2]))top2--;
		stack2[++top2]=a[i];
	}
	int now1=1;int now2=1;
	for(int i=-2*n;i<=n*2;i++){
		while(now1=w(stack1[now1],i))now1++;
		while(now2
思维计算几何凸包

相关

7个方法教你培养“成长型思维”

【人工智能导论：模型与算法】第六章 思维导图

The 2021 CCPC Guilin Onsite【A,I,G(二分),D（思维+构造）,E（最短路】

codeforces和atcoder的思维题目

10张思维导图带你学习Java​Script

用象棋的思维趣说IT人的职业发展和钱途

思维&榜样

Redis 思维导图 (解析版)

计算几何 / Geometry（ACM-Template 2.0）

程序设计思维与实践 Week3 作业 (3/4/数据班)

告别传统工业互联网，提高数字管控思维：三维组态分布式能源站

12月读书笔记3《程序员的思维训练》

标签