$分析$
首先证明一个根本看不出来的结论,在可以合法分段的情况下,最后一段长度尽量小最优。
运用数学归纳法,假设我们已经论证了前 $n- 1$ 种情况,现在要证明长度为 $n$ 的情况。
上图中从上到下一次为编号 $1$ 到 $5$ 的方案。
对于原方案 $1$,若方案 $2$ 存在,则方案 $5$ 一定存在并且优于方案 $1$ 更新。
若方案 $3$ 存在,则构造方案 $4$,则 $w(1) > w(4) > w(3)$,更新。
综上所述,最后一段长度尽量小最优。
然后用单调队列优化 $dp$ 即可。
$代码$
#include <bits/stdc++.h>
using namespace std;
const int N = 40000010, mod = 1 << 30;
int a[N], b[N], g[N], q[N];
long long s[N];
long long val(int x) {
return 2 * s[x] - s[g[x]];
}
int main() {
int n, type;
scanf("%d%d", &n, &type);
if (type == 0) {
for (int i = 1; i <= n; i ++ ) {
scanf("%d", &a[i]);
s[i] = s[i - 1] + a[i];
}
} else {
int x, y, z, m;
scanf("%d%d%d%d%d%d", &x, &y, &z, &b[1], &b[2], &m);
for (int i = 3; i <= n; i ++ ) b[i] = (1ll * b[i - 1] * x % mod + 1ll * b[i - 2] * y % mod + z) % mod;
for (int i = 1, la = 0; i <= m; i ++ ) {
int p, l, r;
scanf("%d%d%d", &p, &l, &r);
for (int j = la + 1; j <= p; j ++ )
a[j] = b[j] % (r - l + 1) + l;
la = p;
}
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
}
int hh = 1, tt = 0;
for (int i = 1; i <= n; i ++ ) {
while (hh <= tt && s[i] >= val(q[hh])) hh ++ ;
if (i != 1) hh -- ;
g[i] = q[hh];
while (hh <= tt && val(q[tt]) >= val(i)) tt -- ;
q[++ tt] = i;
}
int p = n;
__int128 ans = 0, tmp;
while (p) {
tmp = s[p] - s[g[p]];
ans += tmp * tmp;
p = g[p];
}
vector<int> v;
while (ans) {v.push_back(ans % 10); ans /= 10;}
while (v.size()) {
printf("%d", v.back());
v.pop_back();
}
return 0;
}