（CSDN 真的很丑，广告很多QAQ，以后还是回洛谷和 cnblog 了）
Preface
这个问题可以算是卡常卡空间比赛。qwq，在线膜拜考场 AC 巨佬 Orz
Analysis
这道题和 [CF229D]Towers 可以说，除了恶心人的数据几乎一模一样awa
- 法一： 36 p t s 36pts 36pts
首先，前缀和数组 s s s 求出来。
对于 n ≤ 500 n \le 500 n≤500，显然直接用 O ( N 3 ) O(N^3) O(N3) 的区间 DP 即可。
- 法二： 64 p t s 64pts 64pts
如果你想欺骗更多的分数，你还需要观察一个性质：当最后一段尽可能小时，答案必须是最好的。
虽然这种性质可能看不出来，但大家应该都知道为什么。
传统的区间 DP 显然，我不能通过这个问题。考虑换一个 DP 状态：
设 d p ( i , j ) dp(i,j) dp(i,j) 表示当前第 i i i 这段数字的开头是 j 1 j 1 j 1 最小答案。
则有 d p ( i , j ) = min { d p ( j , k ) } + ( s i − s j ) 2 dp(i,j) = \min{\{dp(j,k) \}} + (s_i - s_j) ^ 2 dp(i,j)=min{ dp(j,k)}+(si−sj)2
其中 k k k 要满足 s j − s k ≤ s i − s j s_j - s_k \le s_i - s_j sj−sk≤si−sj
虽然这样仍是 O ( N 3 ) O(N^3) O(N3) 的，但它有一些神奇的性质。
首先根据上述结论， k k k 越大， d p ( j , k ) dp(j,k) dp(j,k) 越小，而且 s j − s k s_j - s_k sj−sk 会越小，满足上式的可能性越高。
考虑建立一个数组 p o s pos pos，令 p o s j pos_j posj 为使得 d p ( j , k ) dp(j,k) dp(j,k) 最小的 k k k 的取值。
这时发现可以将 d p dp dp 改为一维， d p ( i ) dp(i) dp(i) 表示 1 ∼ i 1 \sim i 1∼i 的最优划分值。
从大到小枚举 j j j，若满足 s j − s p o s j ≤ s i − s j s_j - s_{pos_j} \le s_i - s_j sj−sposj≤si−sj，则 d p ( i ) = d p ( j ) + ( s i − s j ) 2 dp(i) = dp(j) + (s_i - s_j) ^ 2 dp(i)=dp(j)+(si−sj)2
然后记录一下这个取值，即 p o s i = j pos_i = j posi=j，目标状态即为 d p ( n ) dp(n) dp(n)。
时间复杂度： O ( N 2 ) O(N^2) O(N2)
到这个时候我们已经可以拿到 64 p t s 64 pts 64pts 的大众分了awa
接下来 n = 5 × 1 0 5 n = 5 \times 10^5 n=5×105 是给 O ( N log N ) O(N\log N) O(NlogN) 的决策单调性做法的，然鹅我并不会那种东西 QAQ，有兴趣可以去 [CF229D]Towers 这个题的题解里看看。
下面直接开始正解。
- 法三： 100 p t s 100 pts 100pts
发现限制我们的是 s j − s p o s j ≤ s i − s j s_j - s_{pos_j} \le s_i - s_j sj−sposj≤si−sj 这个东西，考虑把能一起维护的放到一边：
即 2 × s j − s p o s j ≤ s i 2 \times s_j - s_{pos_j} \le s_i 2×sj−sposj≤si
对于每个 i i i，求出最近的满足这个式子的 j j j 即可。
看 n = 4 × 1 0 7 n = 4 \times 10^7 n=4×107 的恐怖范围，加上 s i s_i si 具有单调性，不难想到可以用单调队列优化~
但我们平常学到的都是求最小，怎么求最近呢？
可以用类似滑动窗口的思路解决，两头同时更新。
具体思路是仍照常维护一个 2 × s j − s p o s j 2 \times s_j - s_{pos_j} 2×sj−sposj 单调递增的队列。
在扫到一个 i i i 时，处理一下队首，如果队首和队首后面的元素同时满足这个限制，那么两者一定都能满足 i + 1 ∼ n i+1\sim n i+1∼n 的限制，而且后面这个元素一定比队首晚入队，更优。
那么这个时候，我还要你队首干什么呢？
这就是我们常说的，如果一个选手比你小还比你强，那么你就可以退役了o(╥﹏╥)o
直接删去队首，继续判断直到队列元素数 ≤ 1 \le 1 ≤1 或者不满足这个条件即可。
其他就和普通的单调队列没区别了 (*▽*)
注意的是这题卡时空限制，而且要用 int128 或者高精度，而且 d p dp dp 数组开不下。
只能把 p o s pos pos 数组处理出来，最后统一计算输出QAQ
时间复杂度： O ( N ) O(N) O(N)
#include <bits/stdc++.h>
#define LL __int128
using namespace std;
const int maxn = 4e7 + 5;
const int maxm = 1e5 +5;
typedef long long ll;
LL read() {
LL s = 0,f = 1;
char c = getchar();
for(;!isdigit(c);c = getchar())
if(c == '-')f = -1;
for(;isdigit(c);c = getchar())s = (s << 1) + (s << 3) + (c ^ '0');
return s * f;
}
void write(LL x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9)write(x / 10);
putchar(x % 10 + '0');
return ;
}
int x,y,z;
int b[maxn];
ll s[maxn];
int a[maxn],m,n,pos[maxn];
int p[maxm],l[maxm],r[maxm];
int q[maxn],head,tail;
ll SUM(int x) {
return s[x] - s[pos[x]] + s[x];
}
void datamaker() {
scanf("%d%d%d%d%d%d",&x,&y,&z,&b[1],&b[2],&m);
for(int i = 1;i <= m;++ i)scanf("%d%d%d",&p[i],&l[i],&r[i]);
for(int i = 3;i <= n;++ i)b[i] = (x * b[i - 1] + y * b[i - 2] + z) & ((1 << 30) - 1);
for(int j = 1;j <= m;++ j) {
for(int i = p[j - 1] + 1;i <= p[j];++ i) {
a[i] = (b[i] % (r[j] - l[j] + 1)) + l[j];
s[i] = s[i - 1] + a[i];
}
}
return ;
}
int main() {
int tp;
scanf("%d%d",&n,&tp);
if(tp)datamaker();
else for(int i = 1;i <= n;++ i)scanf("%d",&a[i]),s[i] = s[i - 1] + a[i];
q[head = tail = 1] = 0;
for(int i = 1;i <= n;++ i) {
for(;head < tail&&SUM(q[head]) <= s[i]&&SUM(q[head + 1]) <= s[i];)q[head ++] = 0;
pos[i] = q[head];
for(;head < tail&&SUM(q[tail]) >= SUM(i);)q[tail --] = 0;
q[++ tail] = i;
}
LL ans = 0;
for(int cur = n;cur;cur = pos[cur])ans += ((LL)(s[cur] - s[pos[cur]]) * (s[cur] - s[pos[cur]]));
write(ans);
return 0;
}
完结撒花★,°:.☆(￣▽￣)/$:.°★ 。