洛谷P5665 [CSP-S2019] 划分题解

题目链接：P5665 [CSP-S2019] 划分

题意：

2048 年，第三十届 CSP 认证的考场上，作为选手的小明打开了第一题。这个题的样例有 $n$ 组数据，数据从 $1 \sim n$ 编号，$i$ 号数据的规模为 $a_i$。

小明对该题设计出了一个暴力程序，对于一组规模为 $u$ 的数据，该程序的运行时间为 $u^2$。然而这个程序运行完一组规模为 $u$ 的数据之后，它将在任何一组规模小于 $u$ 的数据上运行错误。样例中的 $a_i$ 不一定递增，但小明又想在不修改程序的情况下正确运行样例，于是小明决定使用一种非常原始的解决方案：将所有数据划分成若干个数据段，段内数据编号连续，接着将同一段内的数据合并成新数据，其规模等于段内原数据的规模之和，小明将让新数据的规模能够递增。

也就是说，小明需要找到一些分界点 $1 \leq k_1 \lt k_2 \lt \cdots \lt k_p \lt n$，使得
$\sum_{i=1}^{k_1} a_i \leq \sum_{i=k_1+1}^{k_2} a_i \leq \cdots \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 + \cdots + (\sum_{i=k_p+1}^{n} a_i)^2$
小明觉得这个问题非常有趣，并向你请教：给定 $n$ 和 $a_i$，请你求出最优划分方案下，小明的程序的最小运行时间。

输入格式：

由于本题的数据范围较大，部分测试点的 $a_i$ 将在程序内生成。

第一行两个整数 $n, \mathrm{type}$。$n$ 的意义见题目描述，$\mathrm{type}$ 表示输入方式。

若 $\mathrm{type} = 0$，则该测试点的 $a_i$ 直接给出。输入文件接下来：第二行 $n$ 个以空格分隔的整数 $a_i$，表示每组数据的规模。

若 $\mathrm{type} = 1$，则该测试点的 $a_i$ 将特殊生成，生成方式见后文。输入文件接下来：第二行六个以空格分隔的整数 $x, y, z, b_1, b_2, m$。接下来 $m$ 行中，第 $i (1 \leq i \leq m)$ 行包含三个以空格分隔的正整数 $p_i, l_i, r_i$。

对于 $\mathrm{type} = 1$ 的 23~25 号测试点，$a_i$ 的生成方式如下：

给定整数 $x, y, z, b_1, b_2, m$，以及 $m$ 个三元组 $(p_i, l_i, r_i)$。

保证 $n \geq 2$。若 $n \gt 2$，则 $\forall 3 \leq i \leq n, b_i = (x \times b_{i−1} + y \times b_{i−2} + z) \mod 2^{30}$。

保证 $1 \leq p_i \leq n, p_m = n$。令 $p_0 = 0$，则 $p_i$ 还满足 $\forall 0 \leq i \lt m$ 有 $p_i \lt p_{i+1}$。

对于所有 $1 \leq j \leq m$，若下标值 $i~(1 \leq i \leq n)$满足 $p_{j−1} \lt i \leq p_j$，则有
$a_i = \left(b_i \bmod \left( r_j − l_j + 1 \right) \right) + l_j$
上述数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生成方式。

输出格式：

输出一行一个整数，表示答案。

数据范围：

测试点编号 $n \leq$ $a_i \leq$ $\mathrm{type} =$

$1 \sim 3$ $10$ $10$ $0$

$4 \sim 6$ $50$ $10^3$ $0$

$7 \sim 9$ $400$ $10^4$ $0$

$10 \sim 16$ $5000$ $10^5$ $0$

$17 \sim 22$ $5 \times 10^5$ $10^6$ $0$

$23 \sim 25$ $4 \times 10^7$ $10^9$ $1$

$\mathrm{type} \in \{0,1\},~2 \leq n \leq 4 \times 10^7,~1 \leq a_i \leq 10^9$ 。

$1 \leq m \leq 10^5,~1 \leq l_i \leq r_i \leq 10^9,~0 \leq x,y,z,b_1,b_2 \lt 2^{30}$。

测试点编号	$n \leq$	$a_i \leq$	$\mathrm{type} =$
$1 \sim 3$	$10$	$10$	$0$
$4 \sim 6$	$50$	$10^3$	$0$
$7 \sim 9$	$400$	$10^4$	$0$
$10 \sim 16$	$5000$	$10^5$	$0$
$17 \sim 22$	$5 \times 10^5$	$10^6$	$0$
$23 \sim 25$	$4 \times 10^7$	$10^9$	$1$

本题难度虚高。考虑 $n\le 400$ 的暴力dp，枚举分界点有

$f(j,k) = \min\{f(i,j) + (S_k - S_j)^2\}$

优化就是单调队列的板子。就 $23\sim25$ 的测试点比较麻烦。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6 + 15)
    char buf1[SIZ], *p1, *p2;
    char readchar()
    { 
        if(p1 == p2) { p1 = buf1, p2 = buf1 + fread(buf1, 1, SIZ, stdin); }
        return p1 == p2 ? EOF : *p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch = gc(); T x = 0, f = 1; while(!isdigit(ch)) { if(ch == '-') { f = -1; } ch = gc(); }
        while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = gc(); } k = x * f;
    }
    template<typename A, typename ...B> void read(A &x, B &...y) { return read(x), read(y...); }
    template<typename T>void write(T k)
    {
        if(k < 0){ k = -k; pc('-'); } static T stk[66]; T top = 0;
        do{ stk[top++] = k % 10, k /= 10; } while(k); while(top) { pc(stk[--top] + '0'); }
    }
}using namespace FastIO;
#define N ((int)(4e7 + 15))
#define M ((int)(1e5 + 15))

int n, type, a[N], b[N], p[M], l[M], r[M], q[N], pre[N]; ll sum[N];
ll d(int x) { return sum[x] - sum[pre[x]]; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n, type);
    if(type)
    {
        int x, y, z, m; const int mod = (1 << 30) - 1;
        read(x, y, z, b[1], b[2], m);
        rep(i, 1, m) read(p[i], l[i], r[i]);
        rep(i, 3, n) { b[i] = (0ll + 1ll * b[i - 1] * x + 1ll * b[i - 2] * y + z) & mod; }
        rep(i, 1, m) rep(j, p[i - 1] + 1, p[i])
            { a[j] = (b[j] % (r[i] - l[i] + 1)) + l[i]; sum[j] = sum[j - 1] + a[j]; }
    }else { rep(i, 1, n) { read(a[i]); sum[i] = sum[i - 1] + a[i]; } }
    int st, en; q[st = en = 1] = 0;
    rep(i, 1, n)
    {
        while(st < en && d(q[st + 1]) + sum[q[st + 1]] <= sum[i]) ++st;
        pre[i] = q[st];
        while(st < en && d(q[en]) + sum[q[en]] >= d(i) + sum[i]) --en;
        q[++en] = i;
    }
    int now = n; __int128 res = 0, tmp = 1;
    while(now) { tmp = d(now); tmp *= d(now); res += tmp; now = pre[now]; }
    write(res); pc('\n');
    return 0;
}