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)$ 的最大值。