description

analysis

首先有一个结论，对于\([1,i]\)区间划分最后一段的和尽量小，答案会更优，具体证明参考毛爷爷的博客
设\(f[i]\)为满足\([1,i]\)划分最优时、\((f[i],i]\)这段和最小时的最右的端点，最优划分即为从\(n\)开始向\(f\)不断统计
由后一段比前一段大可知\(sum[f[i]]-sum[f[f[i]]]≤sum[i]-sum[f[i]]\)，即\(sum[i]≥2sum[f[i]]-sum[f[f[i]]]\)
右边只和\(f[i]\)有关，把右边的记为\(clac(f[i])\)，于是可以维护一个\(clac\)值上升的单调队列来求出每一位的\(f\)
具体维护就是，队头不断出队直到\(sum[i]<clac(q[head])\)（因为\(f[i]\)要尽可能大），\(f[i]\)赋为队头
若\(clac(i)≤clac(q[tail])\)队尾再不断出队（因为\(clac(i)\)更小且\(i\)更靠右），最后\(i\)进队，就完成了队列的维护

code

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define MAXN 40000005

#define ha 1073741824

#define ll long long

#define LL __int128

#define reg register int

#define fo(i,a,b) for (reg i=a;i<=b;++i)

#define fd(i,a,b) for (reg i=a;i>=b;--i)

using namespace std;

int p[100005],l[100005],r[100005];

int f[MAXN],q[MAXN];

ll b[MAXN],sum[MAXN];

int n,type;

inline int read()

{

	ll x=0,f=1;char ch=getchar();

	while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}

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

	return x*f;

}

inline ll clac(ll x){return 2*sum[x]-sum[f[x]];}

inline void print(LL x)

{

	int num[55];num[0]=0;

	while (x)num[++num[0]]=x%10,x/=10;

	while (num[0])printf("%d",num[num[0]--]);

	printf("\n");

}

int main()

{

	n=read(),type=read();

	if (type)

	{

		int x=read(),y=read(),z=read();b[1]=read(),b[2]=read();int m=read(),now=1;

		fo(i,1,m)p[i]=read(),l[i]=read(),r[i]=read();

		fo(i,3,n)b[i]=(x*b[i-1]%ha+y*b[i-2]%ha+z)%ha;

		fo(i,1,n)

		{

			if (i>p[now])++now;

			sum[i]=sum[i-1]+(b[i]%(r[now]-l[now]+1))+l[now];

		}

	}

	else {fo(i,1,n)sum[i]=sum[i-1]+read();}

	int head=0,tail=0;

	fo(i,1,n)

	{

		while (head<tail && sum[i]>=clac(q[head+1]))++head;

		f[i]=q[head];

		while (head<tail && clac(i)<=clac(q[tail]))--tail;

		q[++tail]=i;

	}

	LL ans=0;

	for (reg i=n;i;i=f[i])ans+=(LL)(sum[i]-sum[f[i]])*(sum[i]-sum[f[i]]);

	print(ans);

	return 0;

}

巴特西

【JZOJ6434】【luoguP5665】【CSP-S2019】划分

description

analysis

code

最新文章

热门文章