$[CSP-S 2019 D2T2]$ : # 划分

题目描述

给你一个序列 把它分成无数段 使得每段的和是递增的 求每段和的平方的和的最小值。
即: $\sum_{i=1}^k (\sum_{j=l_i}^{r_i} a_j)^2$
(k是分成的段数)

$n \le 4*10^7$ 可怕，正解必然O(n)了。

算法1

(暴力枚举) 指数级瞎草

指数级草过3个点。

算法2

(朴素dp) $O(n^3)$

可以过9个点。

$f_{i,j}$表示前i个，分成j段的最小花费。
$g_{i,j}$表示前i个，分成j段，最小花费的最右断点。

$f_{i,j}=min(f_{k,j-1}+(sum[i]-sum[k])^2)$ $(k<i且 {sum_i}-{sum_k} \ge sum_k-sum_{g_{k,j-1}} )$

或者还有一种方法
$f_{i,j}$表示前i个，最后一个断点是j。
$f_{i,j}=min(f_{j,k}+(sum[i]-sum[j])^2)$ $(k<i且 {sum_i}-{sum_j} \ge sum_j-sum_{k} )$

算法3

(优化dp) $O(n^2)$

可以过16个点。

感性理解得 意思就是把一段长的区间分成尽可能多的短的区间之后，答案一定会变优。 显然最后一段越短，越优。

题目实际上并不要求段数。
设g(i)是前i个 最后一个区间所选的断点，
$g_i=max(j|j<i且{sum_i}-{sum_j} \ge sum_j-sum_{g_j})$

$f_i=f_{g_i} + (sum_i - sum_{g_i})^2$

这是$O(n^2)$的

算法4

(单调队列优化dp) $O(n)$

n方dp离正解只差一步之遥。这题需要高精度，不过没有职业精神的我直接__int128。

${sum_i}-{sum_j} \ge sum_j-sum_{g_j}$

${sum_i} \ge 2sum_j-sum_{g_j}$

因为$sum_i$是单调递增的，
所以可以用单调队列维护 $2sum_j-sum_{g_j}$
可以在$O(n)$时间内求出所有$g_i$

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
#define rd(x) scanf("%d",&x)
typedef long long ll;
const int N=4e7+10,M=1e5+10;
int n,g[N],q[N],p[M],l[M],r[M],b[N];
ll s[N];
ll calc(int x){ return 2ll*s[x]-s[g[x]]; } 
__int128 p2(__int128 x){ return x*x; }
void print(__int128 x){
    if(!x) return;
    if(x<0) x=-x,putchar('-');
    print(x/10);
    putchar(x%10+'0');
} 
int main(){
    int tp;rd(n);rd(tp);
    if(!tp){
        rep(i,1,n) scanf("%lld",&s[i]),s[i]+=s[i-1];
    } else {
        int x,y,z,m;
        rd(x);rd(y);rd(z);rd(b[1]);rd(b[2]);rd(m);
        int mod=1ll<<30;
        rep(i,3,n) b[i]=(0ll*1ll*x*b[i-1]%mod+1ll*y*b[i-2]%mod+z)%mod;
        rep(i,1,m){
            rd(p[i]);rd(l[i]);rd(r[i]);
            rep(j,p[i-1]+1,p[i])
                s[j]=b[j]%(r[i]-l[i]+1)+l[i]+s[j-1];
        }
    }
    int hd=1,tl=1;
    rep(i,1,n){
        while(hd<tl&&calc(q[hd+1])<=s[i]) hd++;//满足条件的距离最近的决策点 
        g[i]=q[hd];
        while(hd<tl&&calc(q[tl])>=calc(i)) tl--;
        q[++tl]=i;
    }
    int nw=n;
    __int128 ans=0; 
    while(nw){
        __int128 x=s[nw]-s[g[nw]];
        ans+=p2(x);
        nw=g[nw];
    }
    print(ans);
    return 0;
}