题解：P5665 [CSP-S2019] 划分

· · 题解

因为 (a+b)^2 \ge a^2 + b^2，所以要尽可能多分段。

令 sum_{i,j} 表示 [i,j] 的区间和，pre_{i} 表示 i 的前缀和。

若 sum_{a,b}+sum_{c,d} \le sum_{e,f}，则 (sum_{a,b}+sum_{c,d})^2+{sum_{e,f}}^2 \le {sum_{a,b}}^2+(sum_{c,d}sum_{e,f})^2，那么说明一个区间与前面合并一定优于与后面合并。

所以最后一段要尽可能的小。

设 f_i 表示前 i 个数的答案，g_i 表示前 i 个数最优情况下划分的最后一段的左端点。

那么对于 i，我们需要找到最大的 j，使得 sum_{j+1,i}\ge sum_{g_j,j}。

两边同时加 pre_{j}，得到 pre_{i}\ge 2\times pre_{j}-pre_{{g_j}-1}。

由于 pre_i 单调不减，所以显然可以单调队列优化。

对于任意的 x\le y，若 2\times pre_{x}-pre_{{g_x}-1}\ge 2\times pre_{y}-pre_{{g_y}-1}，那么无论在什么情况下 x 都不会被选择，直接踢出单调队列。

所以单调队列里的元素一定是根据 2\times pre_{i}-pre_{{g_i}-1} 单增的。

每个元素最多分别进出单调队列一次，时间复杂度 O(n)。

int n; bool ty;
ULL pre[N];
__int128 ans;
int b[N],p[M],l[M],r[M];
int q[N],g[N];
LL calc(int p){return 2*pre[p]-pre[g[p]-1];}
void solve(){
    cin>>n>>ty;
    if(!ty){
        ULL a;
        for1(i,1,n) {rin(a); pre[i]=pre[i-1]+a;}
    }else{
        int x,y,z,m;
        cin>>x>>y>>z>>b[1]>>b[2]>>m;
        for1(i,1,m) cin>>p[i]>>l[i]>>r[i];
        for1(i,3,n) b[i]=(1ll*b[i-1]*x+1ll*b[i-2]*y+z)%mod;
        for1(i,1,m)
            for1(j,p[i-1]+1,p[i])
                pre[j]=pre[j-1]+b[j]%(r[i]-l[i]+1)+l[i];
    }
    int h=1,t=1;
    for1(i,1,n){
        while(pre[i]>=calc(q[h+1])&&h<t) h++;
        g[i]=q[h]+1;
        while(calc(i)<=calc(q[t])&&h<=t) t--;
        q[++t]=i;
    }
    int pos=n;
    while(pos){
        __int128 qwq=pre[pos]-pre[g[pos]-1];
        ans+=qwq*qwq;
        pos=g[pos]-1;
    }
    rout(ans);
    return ;
}