更好的阅读体验

Statement

给定一个长为 $n$ 的序列 $a_i$ ，对于一组规模为 $u$ 的数据，代价为 $u^2$ .你需要找到一些分界点 $1\leq k_1<k_2<…<n$ ，使得：
$$ \sum_{i=1}^{k_1}a_i\leq \sum_{i=k_1+1}^{k_2} a_i\leq \dots\leq \sum_{i=k_p+1}^n a_i $$
$p$ 可以为 $0$ 且此时 $k_0=0$ .然后要求最小化：:
$$ (\sum_{i=1}^{k_1}a_i)^2+(\sum_{i=k_1+1}^{k_2}a_i)^2+\dots +(\sum_{i=k_p+1}^n a_i)^2 $$
求这个最小的值。

（数据生成方式见题面）

$n\leq 4e7,1\leq a_i\leq 1e9,1\leq m\leq 1e5,1\leq l_i\leq r_i\leq 1e9,0\leq x,y,z,b_1,b_2\leq 2^{30}$

Thoughts & Solution

难想好写的典型案例（其实也不难……）

一个显然的想法是DP分组。由于这道题跟组数没有关系，所以可以修改一下常规的式子。

设 $f[i][j]$ 为对前 $i$ 个进行分组，最后一组为 $[j+1,i]$ 的最小代价，$sum[i]$ 为序列前缀和。

有方程：
$$ f[i][j]=\min\{f[k][j]+(\sum_{l=j+1}^ia_l)^2\}=\min\{f[k][j]+(sum[i]-sum[j])^2\} $$
复杂度为 $\mathcal{O}(n^3)$ .问题出在上一个断点要一个一个枚举 $k$ 得到。考虑如何加速这个过程。

注意到 “平方之和”一定比 “和的平方”要小。所以把最后一段拆成几段（在满足递增的情况下）答案一定不会变劣。

也就是说最优解的方案一定是合法的里面 最后一段最短 的一种。

那么这时候的 $k$ 就是确定的，数组就省掉了一维变成 $f[i]$ .记录一个 $las[i]$ 表示 $f[i]$ 的方案中上一段的末尾。

方程就是：
$$ f[i]=\min\{f[j]+(s[i]-s[j])^2\},\\\\ j 满足 sum[j]-sum[las[j]]\leq sum[i]-sum[j]. $$
复杂度 $\mathcal{O}(n^2)$ 。这样已经实现了36分到64分的巨大飞跃（

然而对于 $n\leq 4e7$ ，加上常数的话复杂度得是线性的……继续优化。:pensive:

注意上面的 $j$ 的条件式。
$$ sum[j]-sum[las[j]]\leq sum[i]-sum[j]=>sum[i]\ge 2\times sum[j]-sum[las[j]] $$
是不是清新可人的样子 你会发现如果一个 $j$ 对于 $i$ 满足上式，由于前缀和递增，显然对 $i+1$ 也满足上式，因此可行决策点的范围一定是左端点为 $1$ 的一个区间，且随着 $i$ 的增大，这个区间的右端点递增（显然）。

我们用一个函数 $g(j)=2\times sum[j]-sum[las[j]]$ 来表示右式的值。根据题意，显然 $j$ 的位置越靠右越优。

那么，如果有 $j$$<$$j’$ 且 $g(j)>g(j’)$ ，$j’$ 一定比 $j$ 优，$j$ 就是没用的了。

到这里，优化方式已经呼之欲出——单调队列！朴素想法就是在这个 $j$ 单增 $g(j)$ 单增的队列里面进行二分。但是这样还有一个 $\log$ .

再考虑左式 $sum[i]$ 的单调递增性质， 发现如果有一个点 $j$ 对当前点 $i$ 已经合法，可以进行转移了，那么 $j$ 之前的点虽然能用，但是显然没有 $j$ 好用，就可以丢掉了。所以每次从队头弹出直到留下最后一个合法点即可。

每个点只会入队一次出队一次，均摊一下，转移复杂度就是 $\mathcal{O}(1)$ 的，总复杂度 $\mathcal{O}(n)$ . 数据范围诚不欺我

LOJ AC链接 给大家讲个笑话，这道题我同一份代码（去掉文件头了）在 ACWing 上重复提交四次能得到1次RE的好成绩（

卡空间就有点过分，不过考虑到 OJ 确实开不起这么大的空间也可以理解，就是出题人太恶心。（包括这个 __int128 的离谱操作）

所以希望大家这道题尽量一次写对，避免把评测机搞炸给 y 总添麻烦(

//Author: RingweEH
const int N=4e7+10,M=1e5+10;
int n,las[N],p[M],l[M],r[M],typ,que[N];
ll a[N];

ll g( int x )
{
    return a[x]*2-a[las[x]];
}

int main()
{
//freopen( "partition.in","r",stdin ); freopen( "partition.out","w",stdout );

    n=read(); typ=read();
    if ( typ==0 )
    {
        for ( int i=1; i<=n; i++ )
            scanf( "%lld",&a[i] );
    }
    else
    {
        ll x,y,z; scanf( "%lld%lld%lld",&x,&y,&z );
        int now=0,b[2],m; scanf( "%d%d%d",&b[0],&b[1],&m );
        for ( int i=1; i<=m; i++ )
            scanf( "%d%d%d",&p[i],&l[i],&r[i] );
        for ( int i=1; i<=n; i++ )
        {
            while ( p[now]<i ) now++;
            if ( i<=2 ) a[i]=b[i-1]%(r[now]-l[now]+1)+l[now];
            else
            {
                b[0]^=b[1]^=(b[0]=(y*b[0]+x*b[1]+z)%(1<<30))^=b[1];
                a[i]=b[1]%(r[now]-l[now]+1)+l[now];
            }
        }
    }

    for ( int i=1; i<=n; i++ )
        a[i]+=a[i-1];
    int l=0,r=0;
    for ( int i=1; i<=n; i++ )
    {
        while ( l<r && g(que[l+1])<=a[i] ) l++;
        las[i]=que[l];
        while ( l<r && g(que[r])>=g(i) ) r--;
        que[++r]=i; 
    }

    I128 ans=0;
    while ( n ) ans+=(I128)(a[n]-a[las[n]])*(a[n]-a[las[n]]),n=las[n];
    int cnt=0;
    do
    {
        que[++cnt]=ans%10; ans/=10;
    }while ( ans );
    do
    {
        printf( "%d",que[cnt] ); cnt--;
    }while ( cnt );

//fclose( stdin ); fclose( stdout );
//    return 0;
}