CWOI S C0229 C 旅行

题意使用 openssl enc -aes256 -pbkdf2 加密。

U2FsdGVkX1898XC3LuOkZL/tCBg0hiy4r8JDniRUmSKsok3ef8JyokZsYugOCfcJ
JIM9lRfjQ2X+0oJOTLoc0Hu9JXVPKjn3538W0YegJ+WdDlI3aDRegg7XKIW9QleO
LJl4icbEA0NVqt0AkS2aMHLAQ6dtQIo6xZ1iBi3DWrCRA6CDUHmppzYu/auU6Emi
0uvH3ZbQhh9B9NS7xEBZMh2cYxIXS4nVUrc0MMP1H5r35O1upWDExbasQ7yDaM1y
u2UYxjwbiScgNYfR2ARx/pXOnJd5Yyrgo7vJyx9hQepTXBUGZ3X4dzcBX/WVb+CS
SV1XBlD3LjdwSc8pYaVUJhYg2kG88Wtq9RJLcRfmgBpdzpPnFx5RAXcn3J53Z9VL
wrnNkYYj2cZ9ojsqYq1PlNTgsVogCHKHjxI26YFWZ5+7KVyCs73Hvbc7x6LXSSrN
U40tb9SE6pPT2Y1kjVfctw==

generator

import sys
import random

random.seed(sys.argv[1])

n = 10
K, D = random.randint(1, n), random.randint(1, 5)
print(n, K, D)

H = [random.randint(-5, 5) for i in range(n)]
for i in H:
    print(i, end = ' ')
print()

T = [random.randint(1, n - i) for i in range(1, n)]
for i in T:
    print(i, end = ' ')
print()

解析

如何处理这个 $\left\lfloor\frac{j - i}{K}\right\rfloor$ 呢？一个常见的套路便是把整个 $f$ 按照 $K$ 分段。假设 $K = 4$。

| 0 1 2 3 | 4 5 6 7 | 8 9 10 11 | 12 13 ...

假如当前位置为 $x = 2$，那么不减 $D$ 的位置便是 $[3, 6)$，减一个 $D$ 的位置便是 $[6, 10)$，减两个 $D$ 的位置便是 $[10, 14)$……容易发现这些位置的右端点对 $K$ 取模余数和 $2 \bmod K$ 相等。

我们 dp 转移的来源可以分成这几部分：

| 0 1 2 3 | 4 5 6 7 | 8 9 10 11 | 12 13 ...
      ^   |                     |     ^
      +---+------ T_2 ----------+-----+

• 整块（上图 $[4, 12)$）：我们可以定义 $A(i, j)$ 表示对 $i$ 转移时，第 $j$ 块的最大值，我们只需要维护 $0 \le i \le k$ 的 $A$。用数据结构维护 $A(i, ?)$ 可以做到 $O(\log n)$ 转移。
• 前小段（上图 $[3, 4)$）：这些位置都不需要减 $D$。定义 $B(i, j)$ 表示第 $i$ 块第 $j$ 个位置的值，可以用数据结构维护 $O(\log n)$ 转移，也可以转移是记录以下当前块最大值 $O(1)$ 转移。
• 后小段 （上图 $[12, 14)$），有两种情况，设最后一块与 $x$ 同余的位置为 $j$：
  • $x + T_x + 1 \le j$，此时直接查询 $j$ 前缀最小值。
  • 否则，分成块首到 $j$ 和 $j$ 到 $x + T_x + 1$ 两端查询，后者需要多减一个 $D$。

实现

转移时需要多次查询区间最小值，如果用线段树可能会因为常数过大而 TLE，如何用树状数组维护上述所有信息？

首先是整块，虽然是区间最大值，但是当前块及左边的块并没有赋值，可以当成前缀最大值。前小段也同理，可以当作前缀最大值。后小段的第一种情况也是前缀最大值，而后一种情况则比较巧妙：

| 12 13 14 15 |
     |     ^
-----+-----+

如图，这个例子中，$15$ 是 $x + T_x + 1$ 对应的位置，$13$ 是与 $x$ 同余的位置。首先我们可以查到 $[12, 13)$ 的最大值，然后直接查 $[12, 15)$ 的最大值，因为后者会多减去一个 $D$，所以多查询的那部分不会对结果造成影响。

代码

int main()
{
	const int n = rd();
	const int k = rd();
	const long long d = rd();

	std::vector<long long> h(n);
	for (auto &i : h) i = rd();
	std::vector<int> t(n - 1);
	for (auto &i : t) i = rd();

	int block_cnt = (n + k - 1) / k;
	std::vector<long long> f(n);
	std::vector all_max(k, max_fenwick_tree<long long>(block_cnt));
	std::vector block_max(block_cnt, max_fenwick_tree<long long>(k));

	f[n - 1] = h[n - 1];
	block_max[(n - 1) / k].set((n - 1) % k, f[n - 1]);
	if ((n - 1) % k == 0) {
		for (int i = n - 1; i / k == (n - 1) / k; i++)
			all_max[i % k].set((n - 1) / k, f[n - 1] - ((n - 1) / k) * d);
	}

	for (int i = n - 1; i > 0; ) {
		i--;

		int end = i + t[i] + 1;
		long long res = std::numeric_limits<long long>::min();
		res = std::max(res, all_max[i % k].max(end / k) + i / k * d);
		if (end >= (i / k + 1) * k) 
			res = std::max(res, block_max[i / k].max(k));
		else
			res = std::max(res, block_max[i / k].max(end % k));
		if (end / k != i / k && end % k != 0) {
			if (end % k <= i % k) {
				res = std::max(res, block_max[end / k].max(end % k) 
					       + i / k * d - ((end / k - 1) * d));
			} else {
				if (i % k != 0)
					res = std::max(res, 
						       block_max[end / k].max(i % k) 
						       + i / k * d 
						       - ((end / k - 1) * d));
				res = std::max(res,
					       block_max[end / k].max(end % k) 
					       + i / k * d 
					       - (end / k * d));
			}
		} 
		
		f[i] = res + h[i];
		block_max[i / k].set(i % k, f[i]);

		if (i % k == 0) {
			std::vector<long long> 
				pre_max(k + 1, std::numeric_limits<long long>::min()), 
				back_max(k + 1, std::numeric_limits<long long>::min());
			for (int j = i; j < n && j / k == i / k; j++) {
				pre_max[j - i + 1] = std::max(pre_max[j - i], f[j]);
			}
			for (int j = std::min(n, (i / k + 1) * k); j > i; ) {
				j--;
				back_max[j - i] = std::max(back_max[j - i + 1], f[j]);
			}
			for (int j = i; j / k == i / k; j++) {
				all_max[j % k].set(i / k, std::max(pre_max[j % k] + d, back_max[j % k]) 
						   - (i / k) * d);
			}
		}
	}

	long long ans = 0;
	for (int i = 0; i < n; i++) {
		ans ^= (f[i] + i + 1);
	}
	printf("%lld\n", ans);
}

max_fenwick_tree 是维护前缀最大值的树状数组，函数有 set(i, x) 用于设置第 $i$ 个位置的值，和 max(r) 用于查询 $[0, r)$ 的最大值。