P5665 [CSP-S2019] 划分

难度：省选/NOI-。

考点：单调队列、贪心、前缀和。

题意：

没有题目大意，本题题目描述较长，认真阅读每一个信息。

​ 这个题的样例有 $n$ 组数据，数据从 $1\sim n$ 编号，$i$ 号数据的规模为 $a_i$。

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

​ 也就是说，小明需要找到一些分界点 $1\le k_1<k_2<\cdots <k_p<n$，使得

$$\sum _{i=1}^{k_1}{a}_i\le \sum _{i=k_1+1}^{k_2}{a}_i\le \cdots \le \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,type$。$n$ 的意义见题目描述，$type$ 表示输入方式。

1. 若 $type=0$，则该测试点的 $a_i$ 直接给出。输入文件接下来：第二行 $n$ 个以空格分隔的整数 $a_i$，表示每组数据的规模。
2. 若 $type=1$，则该测试点的 $a_i$ 将特殊生成，生成方式见后文。输入文件接下来：第二行六个以空格分隔的整数 $x,y,z,b_1,b_2,m$。接下来 $m$ 行中，第 $i(1\le i\le m)$ 行包含三个以空格分隔的正整数 $p_i,l_i,r_i$。

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

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

保证 $n\ge 2$。若 $n>2$，则 $\forall 3\le i\le n,b_i=(x\times b_{i-1}+y\times b_{i-2}+z)\mathrm{mod}{2}^{30}$。

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

对于所有 $1\le j\le m$，若下标值 $i(1\le i\le n)$满足 $p_{j-1}<i\le p_j$，则有

$$a_i=\left(b_i\mathrm{mod}\left(r_j-l_j+1\right)\right)+l_j$$

上述数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生成方式。

分析：

一会儿再来看输入输出的方式怎么根据题目的意思去构造数据，先分析分析本题怎么做。

​ 本题前面的 $16$ 个测试点 $n\le 4\times 10^7$，可以使用 DP 的 做法来解决，但后面 $17\sim 25$ 个测试点需要贪心的去思考。

​ 如何使运行时间最小呢？也就是下面这一坨。
$$(\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$$

​ 要从 均值不等式 的角度上进行思考，举个例子：给定一个数字 $100$，如果拆分成 $2$ 份 $50$，那么计算贡献时就是 $50^2+50^2=5000$，但是我们拆分成 $100$ 份 $1$，那么计算贡献就是 $1+1+...+1=100$，受此启发：如果拆分的段数越多越好，而且段与段之间差值越小越好。

​ 假设我们有这样一段， $S_1\le S_2\le ...\le S_m$ ，大胆的猜测一下：肯定希望最后一项即 $S_m$ 越小越好，即最大的和 $S_m$ 越小，那么前面比它小的也会小，也意味着每一段之间的方差值比较小，同时段数也会很多，因为总和一定的情况下，如果最大的和很小，那么分出来的段数也会多。

​ 猜想：要让最后一段的和越小越好。

如果考场上没有往均值不等式去猜出来怎么办？只能拿部分分，没有别的办法。

​ 根据猜想，尝试构造一个方案是的最后段的和越小越好。

​ $s[i]$：表示前 $i$ 个数的和，假设最后一段的右端点是 $i$，前一段右端点为 $j$，最后一段区间就是 $[j+1,i]$，最后一段数字的和就可以用 $S_i-S_j$ 来表示。贪心：我们希望 $j$ 越大越好，代表越靠近 $i$ 。我们可以尝试枚举符合的 $j$。怎么判断是否 $j$ 是否满足条件呢？

​ $j$ 满足条件，当且仅当：存在一个方案，使得 $s[i]-s[j]\ge$ 以 $j$ 结尾这一段的总和。

​ 假设上一段是 $S_k+1$ 为开头，$S_j$ 为结尾的区间 $[S_k,S_j]$，满足 $S_i-S_j\ge S_j-S_k$。$i$ 是希望找到以 $i$ 为结尾最短的一段。

​ 这种定义其它对每一段都合适，假设已经求出来以 $j$ 为结尾最后一段中最短的方案，假设是 $k+1$ 开头是所有方案里面最短的。

​ 假设 $g[j]$ 表示所有以 $j$ 为结尾的方案数，最后一段最短的方案，对应的倒数第二段的结尾。

​ 即：$S_i-S_j\ge S_j-S_{g_j}$。

​ 最后一段的区间就可以表示为 $[g_j+1,g_j+\mathrm{2...}g[j]]$ ，判断是否存在以 $j$ 结尾的方案，$j$ 如果存在，则存在一个方案使得 $S_i-S_j\ge S_j-S_{g_j}$ ，$[j+1,i]$ 的区间和大于等于 $[g_j+1,j]$ 的区间和，所有方案当中最后一段间隔最小的。判断 $j$ 是否存在的话，就可以直接判断是否存在 $S_i-S_j\ge S_j-S_{g_j}$ 就可以了。

​ 常用判断是否存在解的话，常用的方法就是在某个集合当中是否存在至少一个方案，如果存在则解一定存在，例如集合中求最小的一个方案，如果存在至少一个方案，那么这个方案就是解。上述的式子来判断是否存在 $j$ 就可以判断是否满足有至少一种方案满足 $S_i-S_j\ge S_j-S_{g_j}$，如果满足则 $j$ 就必定存在。

​ 这种贪心的 $g_j$ 其实是可以递推出来的，从 $0\sim (i-1)$ 中去枚举 $j$，在所有满足上述式子中取一个最大就为答案，也就是 $g_i$ 的取值，所有符合的条件中满足 $g_i$ 的 $j$ 中最大的一个。

​ 有了这个贪心的思路之后，那这个贪心是否正确的呢？接下来就是关于贪心的证明。

这个贪心的证明，还是相对来说很抽象，需要一定的跳跃性思维。

​ 本题的证明也不是常见证明贪心的思路，通过调整然后使得答案越来越好。而是直接证！

​ 把贪心的思路先绘制出来，每一段的和用编号 $a_1\sim a_n$ 来表示，共有 $n$ 段（倒着来编号，最后会发现比较好证，如下图）

​ 注意，上图绘制的是通过刚刚的贪心思路得到的序列 $A$，每一段都是唯一确定的，每一段都是最大的间隔最短的。

​ 接下来是任意其它的思路的方案序列 $B$，来证明 A 将会是更优。其中每一段的和用 $b_1\sim b_m$ 来表示，共有 $m$ 段。

​ 小的思考细节，$A$ 和 $B$ 的序列划分个数 $n,m$ 可以不一样，因为可以通过合并调整的方式来使得它们一样。举个例子，我们可以设 $n=5,m=4$ 有形如下图的一个序列，我们可以通过让 $b_5=0$，来凑齐相等的段数且不会影响结果，因为 $0^2=0$ 。

​ 这里需要证明些什么呢？假设 $B$ 序列的代价（即每一项 $b_i$ 的平方和）是 $f(B)$，$A$ 序列的代价是 $f(A)$，证明 $f(B)>f(A)$。

​ 如何可以证明出所有其它方案 $f(B_1),f(B_2)...$ 的代价都严格大于贪心方案 $f(A)$，那么就贪心的正确性就有了。

​ 把表达式展开就是求：$\sum _{i=1}^m{b}_i^2>\sum _{i=1}^n{a}_i^2$，要证明就要挖掘一些性质出来。

1. 根据题目的要求，每一段区间平方和要满足前一项严格小于后一段区间平方和，即 $a_1\ge a_2\ge ...\ge a_n\ge 0,a_i\in \mathbb{N}$。

2. $b$ 同上面一样要满足 $b_1\ge b_2\ge ...\ge b_m\ge 0,b_i\in \mathbb{N}$。

3. 不同方案，但是序列总和都是一样，即：$\sum _{i=1}^n{a}_i=\sum _{i=1}^m{b}_i$。

4. 贪心方案是每一段都是选择间隔最短最靠右的，那么 $a_1$ (已经是最靠后的点) 为讨论点，那么 $b_1$ 只会在 $a_1$ 的位置或者前面( 形如下图$1$，确定了 $b_1$ 这个点选点会在 $a_1$ 的前面)，即 $a_1\le b_1$，$a_1$ 最小则最靠右，再分析下一个点 $b_2$。

   图 $1$：
   

   ​ $b_2$ 这个点会在 $a_2$ 的前面吗( $\le a_2$ )？(如下图 2 )，看是否产生矛盾就行，分析一下，假设 $b_2$ 这个点落在了 $a_2$ 之前，同时以 $b_2$ 为结尾的后面一段 $b_3$，就有 $b_2\le a_2$，其中 $a_2$ 结尾被改变了，与贪心方案的描述对不上，因为 $a_2$ 是所有以 $a_1$ 为结尾方案中间隔最小且最早的一段，如果 $a_2$ 不是间隔最小且最早的一段则与描述出现矛盾 (如下图 3)，故 $b_2$ 只会落位在 $a_2$ 的前面。

   图 $2$：

图 3：

$b_3$ 的落位点是同上一样，只会在 $a_3$ 的左边，否则会与贪心方案中最早间隔最小一段描述不符矛盾（如下图 4）。

图 4：

性质：$\exists 1\le k\le n,a_1+a_2+...+a_k\le b_1+b_2+...+b_k$ 。

可以完全抛开原来问题，完全变成一个数学问题了。我们要证明所有「其它」序列 $b[i]$ 都满足 $a_1+a_2+...+a_n\le b_1+b_2+...+b_m$。

本题其实用不上 4 个性质，只需要 1、3、4 就可以了。

1. $a_1\ge a_2\ge ...\ge a_n\ge 0,a_i\in \mathbb{N}$
2. $\sum _{i=1}^n{a}_i=\sum _{i=1}^m{b}_i$
3. $\exists 1\le k\le n,a_1+a_2+...+a_k\le b_1+b_2+...+b_k$

为什么第 2 个性质用不上呢？现在来证明一下，也好证明：

在所有其它 $B$ 方案中，我们可以通过 逐步调整 $B$ 使得 $B$ 不断的靠近 $A$，同时可以保证平方和严格变小。

• $B⟶B_1⟶B_2⟶...⟶A$
• $B>B_1\ge B_2>...>A$
• $A\le B$

本题事先说明，已经完全脱离了原来题目的意思，用数学的方案来证明了贪心的思路是正确的。

什么意思呢？如上我们使用了逐步调整的方式使得 $B$ 不断靠近 $A$，来证明出 $A\le B$，而本题完全是用数学的角度去证明的，但是 B 和 A 分别还是代表着 其它方案 和 贪心方案。但是中间的 $B_1$ 和 $B_2$ 不一定对应着原来问题的某种方案。但这并不影响我们证明。 我们只需要证明 $A<B$ 中间产生的任何状态都与原问题没有任何关系。

证明所有「其它」序列 $b[i]$ 都满足 $a_1+a_2+...+a_n\le b_1+b_2+...+b_m$。

接下来问题就跟原问题没有太大关联了，只需要证明不等式成立即可。

​ 证明之前先要知道序列之间的距离 $D$，其中 $D(A,B)=|a_1-b_2|+|a_2-b_2|+...+|a_n-b_n|$ 的距离，当距离等于 $0$ 的时候，说明每一项都是相等的。

​ 通过一种构造 (调整合并) 的方案，使得 $A$ 和 $B$ 的距离逐步变小，初始的时候，每一项都是一个有限值，每一步方案都让 B 严格变小，经过有限步就必然可以让 $B$ 变成 $A$。可以证明出每次变小，平方和都会变小，所以就可以证明出 $\sum _{i=1}^{n}B1<\sum _{i=1}^{n}B$ 。

​ 怎么构造这种方案呢？怎么将 $B>B_1\ge B_2>...>A$ ？

​ 假设这两个序列 $(A,B)$ 中 $1\sim x-1$ 位置上都是相等的，而到达 $x$ 的位置开始不相等（如下），切每一项的和都满足 $a_i$ 小于等于 $b_i$，满足 $\sum _{i=1}^x{a}_i\le \sum _{i=1}^x{b}_i$ ，即第 $x$ 个位置只能 $a$ 小于 $b$，不可能大于，否则 $a$ 的前缀和就会大于 $b$ 的前缀和不符合贪心方案的设定。

​ $a_1,a_2,...a_x...a_y...a_n$

​ $b_1,b_2,...b_x...b_y...b_n$

​ 那么 $a_x<b_x$，且根据上述的性质 $2$，$a、b$ 序列的总和相等，那必然在 $a$ 序列中有一个数 $a_y>b_y$ 。又由于性质 $1$ 可知，$a$ 序列是递减的，那么就有 $b_x>a_x\ge a_{x+1}\ge a_{x+1}\ge ...\ge a_y>b_y$ 从这个式子中也可以观察得到一些性质，和在一定的情况下，两个数的差越小平方和也会越小。总和就是 $b_x-b_y$，我们尝试将 $b_x-1$ 和 $b_y+1$，那么将会满足 $b_x-1\ge a_x\ge a_{x+1}\ge ...\ge a_y\ge b_y+1$。

​ 仍然满足 $b_x-1\ge b_y+1$，相当于 $b$ 序列中两个数，大的数减去 1和小的数加上 1 之后，还是满足大于等于的情况。

​ 那么怎么证明这个不等式成立的呢？
$$\begin{gathered} b_x^2+b_y^2-(b_x-1{)}^2-(b_y+1{)}^2 \\ =2b_x-1-2b_y-1 \\ =2(b_x-b_y)-2 \end{gathered}$$
由于要满足 $b_x-1\ge b_y+1$，移项后 $b_x-b_y\ge 2$，结合上面的不等式可以发现， $2(b_x-b_y)-2\ge 2$ 。

​ 可以发现在 $b$ 序列当中，要取出「第一个」满足 $a_y>b_y$ 的 $y$，满足其中一个数减 $b_x-1$，另外一个数加 $b_y+1$，平方和每次至少会减去 $2$。每次将比 $a$ 序列大的数 (上面分析中 $a_x$ ) 减去 $1$，比 $a$ 序列小的数 (上面分析中 $a_y$ ) 加上 $1$，所以我们相当于对绝对值的差值 $|a_i-b_i|$ 会变小。

​ 故我们可以发现，每个序列的取出「第一个」满足 $a_y>b_y$ 的 $y$，让序列的差值每次至少减去 $2$，又因为 $n$ 是有限值，所以可以通过若干次操作就可以使得 $D(A,B) = |a_1-b_2| + |a_2 - b_2| + … + |a_n - b_n| $ 值为 $0$，即 $A=B$ 序列。而且 $b$ 序列每次操作至少会让平方和至少减去 $2$，所以每次操作都会让平方进行减少，每一个跟 $a$ 不一样的 $b$ 都可以一系列有限次的操作都会变成 $A$，每一步变化都会严格变小，所以可以发现任何一个 $B>A$。

​ 证明完毕，贪心方案：最后段的和越小越好，正确。

​ 就会满足 $S_i-S_j\ge S_j-S_{g_j}$ ，整理后 $S_i\ge 2S_j-S_{g_j}$ ，因为右边只关乎 $j$ 的可以定义为 $h_j$。

​ 相当于在 $i$ 点的左边找到第一个满足 $S_i\ge h_j$ 的点 $j$。

​ 上述的式子，要求满足的 $j$ 点，可以用 单调队列 来求，为什么呢？

​ （如下图）如果前面的 $j$ 当中存在 $h_k\le h_j$ 的点 $k$，那么就可以将 $j$ 点替换成 $k$ 点，因为我们要找的是最靠右边的 $j$ 。那么相当于如果发现右边存在比他小的数字就进行替换 / 删除，那么整个答案序列会是一个单调递增的序列，故可以用单调队列来维护。

​ 那么我们可以发现找到满足最后一个 $\le S_i$ 的数 $h_j$。可以不用二分，直接用单调队列的单调性来维护，从对头开始删除，只要满足 $\le S_i$ 就一直删除，直到最后一个满足 $\le S_i$ 的数 $h_j$，每个元素最多只会进队和出队一次，均摊下来的时间复杂度是 $O(1)$ 的，总的时间复杂度就是 $O(n)$。

参考代码：

#include <bits/stdc++.h>
#define ll long long
#define BL __int128

const int N = 40000010, MOD = 1 << 30;
int n, type;
int w[N], q[N], g[N]; // 单点贡献 w[], 单调队列 q[], 记录以 i 为结尾最后一个g[j]
ll s[N];              // 前缀和数组

ll get(int k)
{
    return 2 * s[k] - s[g[k]]; // 2s[j] - s[g[j]]
}

void print(BL res)
{
    // 常见的就是 string 抠出来每一位拼接上去
    std::string str;
    while (res)
    {
        str += std::to_string((int)(res % 10));
        res /= 10;
    }
    std::reverse(str.begin(), str.end());
    // std::cout << s << "\n";
    puts(str.c_str());
}

int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
    // 计算空间的技巧
    // int sz = sizeof w + sizeof q + sizeof g + sizeof s;
    // printf("%.2lf \n", sz / 1024.0 / 1024);

    std::cin >> n >> type; // 处理输入数据
    if (type == 0)
    {
        for (int i = 1; i <= n; i++)
            std::cin >> w[i];
    }
    else
    {
        int x, y, z, b1, b2, m, p0 = 0;
        std::cin >> x >> y >> z >> b1 >> b2 >> m; // 按照题意模拟计算输入数据
        while (m--)
        {
            int p, l, r;
            std::cin >> p >> l >> r;
            for (int i = p0 + 1; i <= p; i++)
            {
                w[i] = b1 % (r - l + 1) + l;
                int b3 = (x * (ll)b2 + y * (ll)b1 + z) % MOD;
                b1 = b2, b2 = b3;
            }
            p0 = p;
        }
    }

    // 计算前缀和
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + w[i];

    int hh = 0, tt = 0; // 如果区间都合并成 1 个，可以取 0 ，所以单调队列里头尾指针指向 0 代表队列里面已经存在一个元素 0 。
    for (int i = 1; i <= n; i++)
    {
        while (hh <= tt && s[i] >= get(q[hh])) // get() 就是求出 h = 2*s[j]-s[gj]
            hh++;
        hh--; // 最后一个满足 g[j] <= s[i] 的位置
        g[i] = q[hh];
        while (hh <= tt && get(i) <= get(q[tt]))
            tt--;
        q[++tt] = i;
    }

    // 从后往前倒推出每一个区间
    BL res = 0;
    for (int i = n; i; i = g[i])
    {
        BL sum = s[i] - s[g[i]];
        res += sum * sum;
    }
    // std::cout << res << "\n";
    // __int128需要手动输出
    print(res);

    return 0;
}