题解：P5665 [CSP-S2019] 划分

Mirasycle · 2024-12-24 13:18:48 · 题解

先考虑暴力，设 dp(i,j) 表示最后一段分割在区间 [i,j) 上，那么最暴力的就是 O(n^3) 枚举，我们发现 dp(j,k) \to dp(i,j) 对于每一个 j 可选的 k 集应该是不断增大的，于是我们可以对于每一个 j 单调队列，复杂度 O(n^2)。

其实我们可以配合贪心通过一些数学性质来解决这个问题或者打表，就像方差那题一样。对于这题显然越大的数，平方越大，也就是 (a+b)^2 \ge a^2+b^2，于是我们需要保证最后一段划分尽可能小，也就是这么多段尽可能接近或者说划分更多段。

于是我们设出 f_i 表示前 i 个数的答案，g_i 表示最后一段划分的和。这样只需要每次找到最大的 j 满足 sum_{j+1,i} \ge g_j 进行转移即可。即 pre_i \ge g_j+pre_j，相同变量在一侧，单调队列即可。注意 g_i 不一定大于 g_{i-1}，只是要求大于前一段并不是大于上一个位置。

时间复杂度 O(n)。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=4e7+10;
const int maxm=1e5+10;
const int mod=(1<<30);
long long pre[maxn],g[maxn]; int top=0;
int q[maxn],p[maxm],l[maxm],r[maxm],b[maxn],a[60];
inline long long calc(int x){ return 2*pre[x]-pre[g[x]]; }
inline long long val(int x){ return pre[x]-pre[g[x]]; }
void print(__int128 ans){
    while(ans){
        a[++top]=ans%10;
        ans/=10;
    }
    while(top) cout<<a[top--];
}
int main(){
    int n,type; cin>>n>>type;
    if(!type){
        pre[0]=0;
        for(int i=1;i<=n;i++){
            int x; cin>>x;
            pre[i]=pre[i-1]+x;
        }
    }else{
        int x,y,z,m;
        cin>>x>>y>>z>>b[1]>>b[2]>>m;
        for(int i=1;i<=m;i++) cin>>p[i]>>l[i]>>r[i];
        for(int i=3;i<=n;i++) b[i]=(1ll*b[i-1]*x+1ll*b[i-2]*y+z)%mod;
        for(int i=1;i<=m;i++)
            for(int j=p[i-1]+1;j<=p[i];j++){
                x=b[j]%(r[i]-l[i]+1)+l[i];
                pre[j]=pre[j-1]+x;
            }
    }
    q[0]=0; int l=1,r=1; q[1]=0;
    for(int i=1;i<=n;i++){
        while(pre[i]>=calc(q[l+1])&&l<r) l++;
        g[i]=q[l];
        while(calc(i)<=calc(q[r])&&l<=r) r--;
        q[++r]=i;
    }
    int P=n; __int128 ans=0,mul=1;
    while(P){
        mul=val(P); mul=mul*mul;
        ans=ans+mul; 
        P=g[P];
    }
    print(ans);
    return 0;
}