$\text{Description}$
给定 $\{a_n\}$，求一个对 $\{a_n\}$ 的划分方式，满足每一段的和单调不降，且每一段的和的平方和尽可能小。
$\text{Solution}$
考虑一个动态规划，我们需要前一段的和与当前最小值，先维护一个前缀和 $s_i=\sum_{j=1}^{i}a_j$，所以令 $f_{i,j}$ 表示最后一段是 $(j,i]$ 的最小值，那么有：
这个复杂度是 $O(n^3)$ 的。
考虑对于一个正整数序列 $\{a_n\}$，有 $(\sum_{i=1}^na_i)^2>\sum_{i=1}^na_n^2$，也就是说我们要尽量多分段。
也就是说，令 $g_i$ 表示将 $[1,i]$ 按最优方案划分后，最后一段 $(j,i]$ 的 $j$，我们有：
于是有了个 $O(n^2)$ 的做法。
整理下下标里的不等式，有 $2s_j-s_{g_j}\le s_i$。
令 $w(i)=2s_i-s_{g_i}$，我们要做的就是求：
考虑对于 $i$ ，有 $x<y,w(x)\le s_i,w(y)\le s_i$，则我们肯定选取 $y$。又因为 $s_i$ 是单调递增的，故 $x$ 之后肯定也不如 $y$ ，从而想到维护一个队内元素按 $w$ 单调递减的单调队列，每次先将队头后的 $w$ 比 $s_i$ 小或等的元素删除，之后取出队头作为最优决策，然后将队尾的 $w$ 大于等于当前的 $w$ 的删除，最后插入当前元素。
关于后三个点的高精，在 $\text{OJ}$ 上可以用 $\text{__int128}$ 代替。然后卡常就用用 $\text{fread}$，玄学调 $\text{Buf}$ 数组长度就可以。
$\text{Code}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include<bits/stdc++.h>
#define REG register
#define LL long long
#define IL __int128
#define MAXN 40000005
#define MOD 1073741824
using namespace std;
char buf[1<<17],*p1=buf,*p2=buf;
#define mgetc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<13,stdin),p1==p2)?EOF:*(p1++))
inline LL read(){
REG LL x(0);
static char c=mgetc();
while(!isdigit(c)) c=mgetc();
while(isdigit(c)) x=(x*10)+(c^48),c=mgetc();
return x;
}
int n;
LL s[MAXN];int b[MAXN];
int g[MAXN];
LL Que[MAXN];
int head,tail;
IL ans=0;
inline void Print(IL x){
int st[51]={},top=0;
while(x) st[++top]=x%10,x/=10;
for(REG int i=top;i>=1;--i) putchar(st[i]+48);
}
inline void Input(int type){
if(type){
int x=read(),y=read(),z=read();b[1]=read(),b[2]=read();int m=read();
int lstp=0;
for(REG int i=1;i<=m;++i){
LL p=read(),l=read(),r=read();
for(REG int j=lstp+1;j<=p;++j){
if(!b[j]) b[j]=(((LL)x*b[j-1]%MOD+(LL)y*b[j-2]%MOD)%MOD+z)%MOD;
s[j]=s[j-1]+(LL)b[j]%(r-l+1)+l;
}
lstp=p;
}
}
else
for(REG int i=1;i<=n;++i) s[i]=s[i-1]+read();
}
inline LL W(int pos){return 2*s[pos]-s[g[pos]];}
inline IL Work(){
head=tail=0;
for(REG int i=1;i<=n;++i){
while(head<tail&&W(Que[head+1])<=s[i]) ++head;
g[i]=Que[head];
while(head<tail&&W(Que[tail])>=W(i)) --tail;
Que[++tail]=i;
}
IL ans=0;
int now=n;
while(now){
IL tmp=(s[now]-s[g[now]]);
tmp=tmp*tmp;
ans=ans+tmp;
now=g[now];
}
return ans;
}
int main(){
n=read();
Input(read());
Print(Work());
}
|
