洛谷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}\) 表示输入方式。 1. 若 \(\mathrm{type} = 0\)，则该测试点的 \(a_i\) 直接给出。输入文件接下来：第二行 \(n\) 个以空格分隔的整数 \(a_i\)，表示每组数据的规模。 2. 若 \(\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\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;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/5egn0opj