P5665

Aryper · 2021-10-14 15:29:59 · 个人记录

[CSP-S2019] 划分

先是 DP。然后单调队列可以优化到 O(n^2)。

贪心的策略是最后的那段数之和尽量小（相当于将数尽量均分，尽量少的合并，因为合并一定比不合并亏）。于是可以用一个单调队列维护到这里之前的上一段划分的末尾 g_i。为了方便，比较的函数是 2c_x-c_{g_x}，这样当 2c_t-c_{g_t}\ge2c_i-c_{g_i} 的时候，有 g_i\ge t。

时间复杂度 O(n)。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;

const ll N=4e7,mo=(1ll<<30),M=1e5;

ll n,type,it,h,t,x,y,z,m;

__int128 ans;

int g[N+5],q[N+5];

ll b[N+5],p[2],l,r,c[N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(__int128 x) {
    static char buf[22];static __int128 len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();type=read();

    if(type==0) {
        for(ll i=1;i<=n;i++) {
            c[i]=c[i-1]+read();
        }
    }
    if(type==1) {
        x=read();y=read();z=read();b[1]=read();b[2]=read();m=read();
        for(ll i=3;i<=n;i++) {
            b[i]=(x*b[i-1]+y*b[i-2]+z)%mo;
        }
        for(ll i=1;i<=m;i++) {
            p[i&1]=read();l=read();r=read();
            for(ll j=p[(i-1)&1]+1;j<=p[i&1];j++) {
                c[j]=c[j-1]+(b[j]%(r-l+1))+l;
            }
        }
    }

    h=1;t=1;
    for(ll i=1;i<=n;i++) {
        while(h<t&&2*c[q[h+1]]-c[g[q[h+1]]]<=c[i]) h++;
        g[i]=q[h];
        while(h<t&&2*c[i]-c[g[i]]<=2*c[q[t]]-c[g[q[t]]]) t--;
        q[++t]=i;
    }

    it=n;
    while(it) {
        ans+=((__int128)c[it]-c[g[it]])*(c[it]-c[g[it]]);
        it=g[it];
    }

    write(ans);

    return 0;
}