[CSP-S2 2019]划分 题解

题目地址：洛谷：P5665 划分 – 洛谷 | 计算机科学教育新生态

题目描述

2048 年，第三十届 CSP 认证的考场上，作为选手的小明打开了第一题。这个题的样例有 $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 \dots \le \sum_{i=k_p+1}^n a_i
$$

注意 $p$ 可以为 $0$ 且此时 $k_0 = 0$，也就是小明可以将所有数据合并在一起运行。

小明希望他的程序在正确运行样例情况下，运行时间也能尽量小，也就是最小化

$$
\left(\sum_{i=1}^{k_1} a_i \right)^2+\left(\sum_{i=k_1}^{k_2} a_i \right)^2+\cdots +\left(\sum_{i=k_p+1}^n a_i \right)^2
$$

小明觉得这个问题非常有趣，并向你请教：给定 $n$ 和 $a_i$，请你求出最优划分方案下，小明的程序的最小运行时间。

题意简述

给定一个长度为 $n$ 的数列 $\{a_i\}$，求对数列的一个划分 $T = \{ k_1, k_2, \dots, k_p \}$，使得该划分满足 $\sum\limits_{i=1}^{k_1} a_i\le \sum\limits_{i=k_1+1}^{k_2} a_i \le \dots \le \sum\limits_{i=k_p+1}^n a_i$，且最小化 $ \left(\sum\limits_{i=1}^{k_1} a_i \right)^2+\left(\sum\limits_{i=k_1}^{k_2} a_i \right)^2+\cdots +\left(\sum\limits_{i=k_p+1}^n a_i \right)^2 $。

输入输出格式

输入格式：

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

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

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

对于 $\text{type} = 1$ 的 $23 \sim 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) \bmod 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 \bmod (r_j-l_j+1) \right) +l_j
$$

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

输出格式：

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

输入输出样例

样例 #1

输入样例#1：

5 0
5 1 7 9 9

输出样例#1：

247

样例 #2

输入样例#2：

10 0
5 6 7 7 4 6 2 13 19 9

输出样例#2：

1256

样例 #3

输入样例#3：

10000000 1
123 456 789 12345 6789 3
2000000 123456789 987654321
7000000 234567891 876543219
10000000 456789123 567891234

输出样例#3：

4972194419293431240859891640

数据范围

对于 $\text{type} = 0$ 的测试点，保证答案不超过 $4\times 10^{18}$。

所有测试点满足：$\text{type} \in {0, 1} , 2 \le n \le 4 \times 10^7 , 1 \le a_i \le 10^9 , 1 \le m \le 10^5 ,1 \le l_i \le r_i \le 10^9 , 0 \le x, y, z, b_1, b_2 < 2^{30}$。

题解

参考资料：

• 题解 P5665 【划分】 – syksykCCC’s blog – 洛谷博客
• CSP2019划分的简要题解 – 博客 – matthew99的博客

这个题的部分思路并不难，但最优解法确实具有一定的难度和复杂程度，以至于从开始写到整理思路写这篇题解一共用了三天时间。

最初的 DP

首先可以设计出一个比较简单的 DP，状态 $f(i, j)$ 表示对前 $i$ 个数字分段，上一段的结尾为 $j$ 的时候段平方和的最小值。转移时，枚举上一段的结尾 $j$，再枚举上上一段的结尾 $k$，先判断是否满足转移条件 $\sum\limits_{t=k+1}^j a_t \leq \sum\limits_{t’=j+1}^i a_{t’}$，然后进行最小化转移：

$$ f(i, j) = \min_{ \sum\limits_{t=k+1}^j a_t \leq \sum\limits_{t’=j+1}^i a_{t’} } \left\{ f(j, k) + \left( \sum\limits_{t=j+1}^i a_i \right)^2 \right\} $$

显然这个 DP 的复杂度为 $O(n^3)$。

贪心策略与 DP 优化

看这个式子：

$$ a^2 + b^2 < (a+b)^2 \ \ \ (a, b > 0) $$

在转移时，最后一段最长肯定越可能满足转移条件。当段较长的时候，可能将段从中间拆成多段也可以满足转移条件。假设切为两段后满足转移条件且前一段之和为 $a$、后一段之和为 $b$，上面的式子告诉我们，这里切成两段后的段平方和更小。因此，段肯定是越短越好的，或者也可以说，最后一段越短越好。事实上，段越短有利于之后分的段也较短。

因此，这里有贪心策略：段分得越短越好。

考虑将贪心应用进 DP 的过程中，既然最后一段越短越好，最优解中的最后一段一定是最短的，因此上一段的结尾不再有多种可能性，而是直接选择使最后一段最短的那一个。将前 $i$ 个数字分段的最优解中，上一段的结尾记为 $lst(i)$，DP 状态也可改为 $f(i)$ 代表前 $i$ 个数字分段的最优解的段平方和。转移方程如下：

$$ f(i) = \min_{ \sum\limits_{t=lst(j)+1}^j a_t \leq \sum\limits_{t’=j+1}^i a_{t’} } \left\{ f(j) + \left( \sum\limits_{t=j+1}^i a_i \right)^2 \right\} $$

复杂度降为 $O(n^2)$，但依然不够。

单调队列

记 $a_i$ 的前缀和为 $s(i)$，将转移条件写成前缀和的形式：

$$ s(j)-s[lst(j)-1] \leq s(i)-s(j) $$

移项可得

$$ s(i) \geq 2s(j)-s[lst(j)-1] $$

上式的左边只与 $i$ 有关，右边只与 $j$ 有关，我们需要找到满足上述条件的最大的 $j$。

此外，还可以发现，当一个 $j$ 满足上述条件时，根据前缀和的单增性可以得到 $s(i+1) \geq s(i) \geq 2s(j)-s[lst(j)-1]$，即 $j$ 也可以作为 $i+1$ 的决策。因此可行的决策点是一个以 $1$ 为左端点的区间，当 $i$ 增大时，决策点的区间右端点也是单增的（性质 1）。显然，$2s(j)-s[lst(j)-1]$ 的值越小，$j$ 越可能成为合法的决策点，也就是说，记 $A(j) = 2s(j)-s[lst(j)-1]$，当 $j_1 > j_2$ 且 $A(j_1) \leq A(j_2)$ 时，$j_1$ 一定优于 $j_2$（性质 2）。

上述性质决定了我们可以应用单调队列优化 DP 转移的复杂度：维护一个 $A(j)$ 数值单调递增且 $j$ 也单增的单调队列，每次转移时找到队列中最大的满足上述条件的决策点 $j_m$（性质 1），转移后仅保留 $j_m$ 而弹出小于 $j_m$ 的满足条件的决策点（性质 2）。转移完成后，计算 $A(i)$ 再将 $i$ 放入队列中，作为以后的状态的可能决策点。

利用单调队列优化 DP 后，转移的复杂度变为 $O(1)$，则总复杂度为 $O(n)$，可以通过极限数据。

卡常

由于最开始的写法使用了大量 STL 和常数略大的写法，在各种 OJ 上都跑不过极限数据，于是开始了卡常。

• 首先自然是用了 fread 版快读，这算是我的一个习惯。
• 在高精计算过程中利用特殊条件判断减少了总运算次数，尤其是减少了取模的次数。
• 原本是在输入之后单独算一遍前缀和，改成了边输入边算前缀和。
• 由于有点卡空间，复用了前缀和数组 s 的空间作为生成数据用的临时空间。
• 单调队列没封装，直接把实现展开到 DP 的过程中了。
• 手动开了个 O3。

最后终于在洛谷上 AC 了。不过没卡的这么极端的时候也能在 LOJ、UOJ 之类的地方跑过，可能洛谷跑的会略有点慢。

严谨性说明和性质证明

本题解的说明并不严谨，在说明单调队列优化转移时并未给出相关性质的证明，表述也不尽清晰。本文受本人水平、时间、精力等所限，暂时无法呈现出更好的效果，欢迎提出建议或改写本文部分内容。

关于有关性质的证明，可以在毛爷爷的博客：CSP2019划分的简要题解 – 博客 – matthew99的博客阅读。

代码

#pragma GCC optimize(3) // 手动开 O3
// Code by KSkun, 2019/12
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <utility>

typedef unsigned long long LL;
typedef std::pair<int, int> PII;

inline char fgc() {
	static char buf[100000], * p1 = buf, * p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
		? EOF : *p1++;
}

inline LL readint() {
	register LL res = 0, neg = 1; register char c = fgc();
	for (; !isdigit(c); c = fgc()) if (c == '-') neg = -1;
	for (; isdigit(c); c = fgc()) res = res * 10 + c - '0';
	return res * neg;
}

inline char readsingle() {
	char c;
	while (!isgraph(c = fgc())) {}
	return c;
}

const int MAXN = 40000005, MAXM = 100005;;
const LL MASK = (1ull << 30) - 1; // % 2^30 和 & MARK 等价

int n, type, lst[MAXN];
LL s[MAXN];

void gen_data() {
	LL x, y, z, m;
	x = readint(); y = readint(); z = readint();
	s[1] = readint(); s[2] = readint();
	m = readint();
	int* p = new int[MAXM], * l = new int[MAXM], * r = new int[MAXM];
	p[0] = l[0] = r[0] = 0;
	for (int i = 1; i <= m; i++) {
		p[i] = readint();
		l[i] = readint();
		r[i] = readint();
	}
	for (int i = 3; i <= n; i++) {
		s[i] = (x * s[i - 1] + y * s[i - 2] + z) & MASK; // 复用 s 数组省空间
	}
	for (int i = 1; i <= m; i++) {
		for (int j = p[i - 1] + 1; j <= p[i]; j++) {
			s[j] = (s[j] % (r[i] - l[i] + 1)) + l[i] + s[j - 1]; // 复用 s 数组省空间
		}
	}
	delete[] p; delete[] l; delete[] r; // 内存回收
}

const int BN_MAX = 1e9;
struct BigNum {
	LL dat[5];
	int len;
	BigNum() {
		dat[0] = dat[1] = dat[2] = dat[3] = dat[4] = 0; // 手动初始化没用 memset 减小常数
		len = 0;
	}
	BigNum(LL x) {
		dat[0] = dat[1] = dat[2] = dat[3] = dat[4] = 0;
		len = 0;
		while (x > 0) {
			dat[len++] = x % BN_MAX;
			x /= BN_MAX;
		}
	}

	BigNum operator+(const BigNum& rhs) const {
		BigNum res;
		if (len == 0) return rhs; // 减少运算次数
		if (rhs.len == 0) return *this;

		res.len = std::max(len, rhs.len);
		for (register int i = 0; i < res.len; i++) {
			if (dat[i] == 0 && rhs.dat[i] == 0) continue; // 减少运算次数
			res.dat[i] += dat[i] + rhs.dat[i];
			if (res.dat[i] > BN_MAX) { // 减少运算次数
				res.dat[i + 1] += res.dat[i] / BN_MAX;
				res.dat[i] %= BN_MAX;
			}
		}
		if (res.dat[res.len] != 0) res.len++;
		return res;
	}
	BigNum operator*(const BigNum& rhs) const {
		BigNum res;
		if (len == 0 || rhs.len == 0) return res;

		res.len = len + rhs.len - 1;
		for (register int i = 0; i < len; i++) {
			if (dat[i] == 0) continue; // 减少运算次数
			for (register int j = 0; j < rhs.len; j++) {
				if (rhs.dat[j] == 0) continue; // 减少运算次数
				res.dat[i + j] += dat[i] * rhs.dat[j];
			}
		}
		for (register int i = 0; i < res.len; i++) {
			if (res.dat[i] > BN_MAX) { // 减少运算次数
				res.dat[i + 1] += res.dat[i] / BN_MAX;
				res.dat[i] %= BN_MAX;
			}
		}
		if (res.dat[res.len] != 0) res.len++;
		return res;
	}
};

int d_dat[MAXN], d_l, d_r;

inline LL A(int idx) {
	return 2 * s[idx] - s[lst[idx]];
}

int main() {
	n = readint(); type = readint();

	if (type == 0) {
		for (register int i = 1; i <= n; i++) {
			s[i] = s[i - 1] + readint(); // 输入时就把前缀和做了，减小单独计算的常数
		}
	} else {
		gen_data();
	}

	d_l = d_r = 0; // 单调队列手写而且没封装，常数优化
	for (register int i = 1; i <= n; i++) {
		int lst_ele = 0;
		while (d_l != d_r && s[i] >= A(d_dat[d_l])) {
			lst_ele = d_dat[d_l]; d_l++;
		}
		lst[i] = lst_ele; d_dat[--d_l] = lst_ele;
		LL Ai = A(i); // 没空间存 A 数组，所以用函数，这里是避免重复运算减小常数
		while (d_l != d_r && Ai <= A(d_dat[d_r - 1])) d_r--;
		d_dat[d_r++] = i;
	}

	BigNum ans;
	for (register int i = n; i != 0; i = lst[i]) {
		BigNum t = BigNum(s[i] - s[lst[i]]);
		ans = ans + t * t;
	}
	for (register int i = ans.len - 1; i >= 0; i--) {
		if (i == ans.len - 1) {
			printf("%llu", ans.dat[i]);
		} else {
			printf("%09llu", ans.dat[i]);
		}
	}

	return 0;
}