题解 P5665 【划分【民间数据】】

· · 题解

暂时可以通过洛谷所有数据的不对劲做法，当然在考试的时候并不能得分qwq

先讲一下本题题解：

首先是一个神奇的性质，考虑最后的答案，最优解必然满足最后一段最小。

证明的话可以查看其他的题解，已经有人证过了我就不献丑了。

有了这个结论后我们可以开始考虑 dp 了

令 f_i 表示以 i 结尾的最优方案，那么同时记录一下 l_i 表示以 i 结尾的最小段

由于我们知道最优解是满足最后结尾段最小的情况，又由于对于任意的一个前缀其都满足最优解满足最后段最小，换句话说，我们只需要求出满足此位置 j 结尾的最小段 l_j 比 S_i-S_j 小即可

于是转移合法的判定就呼之而出了：

f_i=f_{\max(j)\in (S_i-S_j\ge l_j)}+(S_i-S_j)^2

简单化简一下条件就是：

S_i\ge S_j+l_j

于是令 R_i=S_i+l_i 就可以很简单的考虑转移了

显然是满足 S_i\ge R_k 中最大的 k，于是单调队列优化一下就可以了

然后由于这里是 Luogu 所以通过 int128 通过这道题 88

下面是关于这道题的不正经搞法

关于变成 1\rm 00pts 值得令人探究的是关于它的空间问题

如果您采取我这个不方便的做法，那么我们最起码需要记 dp 数组，记 \rm sum 数组（前缀和数组）以及 R 数组（用于判定转移）

大概需要压掉其中一个才可以过去。

我们大胆猜测转移的时候被存下来的可以用的状态数并不多，即可以被使用的 dp_k 并不多，所以我们直接把 dp_i 当做 dp_{i\% P} 即可，将 p 设成大概 1e7 即可，这是因为存放在单调队列内的dp 值的数量应该不会超过 1e7，然后通过实践发现这样确实是可以的。

不过官方数据有点毒，大概需要设成 1.5\cdot 10^7 甚至以上才可以。

然后注意 \rm int,long~long,int128 要分开看待也就是说你需要注意变量的使用。

然而即使在以前的 Luogu 这样做也会 \text{TLE}，我们必然是非常不爽的，你需要开 \rm O2 才能过题。

所以我们考虑将取膜运算加速，将 p 选成 2^x 就可以通过 \& 运算简单实现了

适合的模数 P=16,777,215

#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define re register
#define LL __int128
LL gi() { 
    LL cn = 0, flus = 1 ; char cc = getchar() ; 
    while( cc > '9' || cc < '0' ) { if( cc == '-' ) flus = -flus ; cc = getchar() ; } 
    while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ; 
    return cn * flus ; 
} 
const int N = 4e7 + 5 ; 
const int M = 1e5 + 5 ; 
const int P = ( 1 << 30 ) - 1 ; 
const int Y = 16777215 ; 
int n, m, q[N], he, ta ; 
LL dp[Y + 5] ; 
long long sum[N], B[N] ; 
int L[M], R[M], p[M] ; 
LL D( LL x ) { 
    return x * x ; 
} 
void write( LL x ) { 
    if( x == 0 ) return ; 
    write( x / 10 ), printf("%d", x % 10 ) ; 
} 
signed main() { 
    n = gi() ; int type = gi() ; 
    if( type == 0 ) {
        rep( i, 1, n ) sum[i] = gi(), sum[i] = sum[i - 1] + sum[i] ; 
    }
    else {
        LL x, y, z ; 
        x = gi(), y = gi(), z = gi() ;
        sum[1] = gi(), sum[2] = gi(), m = gi() ;
        rep( i, 3, n ) sum[i] = ( x * sum[i - 1] + y * sum[i - 2] + z ) & P ; 
        rep( i, 1, m ) p[i] = gi(), L[i] = gi(), R[i] = gi() ; p[0] = 0 ;
        for( re int t = 1; t <= m; ++ t ) {
            for( re int i = p[t - 1] + 1; i <= p[t]; ++ i ) {
                sum[i] = sum[i] % ( R[t] - L[t] + 1ll ) + L[t] ; 
                sum[i] = sum[i - 1] + sum[i] ; 
            }
        }
    }
    memset( dp, -1, sizeof(dp) ), dp[0] = 0, B[0] = 0, he = 1, q[++ ta] = 0 ; 
    for( re int i = 1; i <= n; ++ i ) { 
        long long Ri = sum[i] ; 
        while( he < ta && Ri >= B[q[he + 1]] ) ++ he ; 
        if( he <= ta ) 
            if( Ri >= B[q[he]] ) {
                dp[i & Y] = dp[q[he] & Y] + D( sum[i] - sum[q[he]] ) ;
                B[i] = sum[i] - sum[q[he]] ; 
                B[i] = sum[i] + B[i] ; 
            }
        if( dp[i & Y] != -1 ) {
            while( he <= ta && B[q[ta]] > B[i] ) -- ta ; 
            q[++ ta] = i ; 
        } 
    } 
    write(dp[n & Y]) ; 
    return 0 ; 
}