AtCoder ABC 456 F Plan Holidays

問題重述

$N$ 天的排程，每天初始非假日。可以重複下面的操作：

1. 花 $A_i$ 元把第 $i$ 天設為假日（任何位置都行）
2. 若第 $i-1$ 跟 $i+1$ 都是假日，可以免費把第 $i$ 天設為假日（$i \in [2, N-1]$）

目標：做出至少 $K$ 天連續假日，最小化總成本。

限制 $N \le 2 \times 10^5$、$K \le N$、$A_i \le 10^9$。

Step 1：免費規則的轉化

免費規則只要相鄰兩個假日中間隔一格，那個空格就會被填滿。 所以如果你買的天數是集合 $S$，只要 S 中相鄰元素差距不超過 2，中間所有空格就會被自動補成假日。

把 $S$ 排序之後設 $s_1 < s_2 < \dots < s_m$，免費規則的等價條件是：

最終覆蓋的範圍會是 $[s_1, s_m]$，連續假日長度為 $s_m - s_1 + 1$。

問題等價成：

選一個位置集合 $S = \{s_1 < \dots < s_m\}$， 滿足 $s_{j+1} - s_j \le 2$ 且 $s_m - s_1 + 1 \ge K$， 最小化 $\sum_{i \in S} A_i$。

Step 2：化為最大不相鄰省略和

假設最終覆蓋區間是 $[s, e]$，長度 $L = e - s + 1$。 兩端 $s$ 跟 $e$ 一定要買（否則覆蓋會更短）。

中間 $[s+1, e-1]$ 的位置中，可以「不買」的條件是：不買的位置之間不能相鄰（否則差距 > 2，違反免費規則）。

換句話說，「不買」的集合是區間 $[s+1, e-1]$ 中的獨立集（任兩個不相鄰）。 要最小化買的總和，就是最大化省下來的金額。

其中 $\mathrm{MNAS}$ 表示「最大不相鄰選和」（Max Non-Adjacent Sum）。

具體驗證

用 Sample 1 試試：$N=5,\ K=2,\ A=[3,1,4,1,5]$。

最佳解 cost = 2，跟答案一致。

Step 3：為什麼只需檢查 L = K 跟 L = K + 1

直覺上，越短的區間 $L$ 越省（買的東西少）；但 $L = K + 1$ 比 $L = K$ 多一格之後， 中間可以多省一個 $A_i$，未必比較貴。

反例：L = K + 1 可以嚴格比較好

$A = [10, 100, 100, 100, 10],\ K = 4$。

• L = K = 4：最佳區間 [1, 4]，cost = (10+100+100+100) − max(MNAS of [100, 100]) = 310 − 100 = 210
• L = K + 1 = 5：區間 [1, 5]，可以買 {1, 3, 5}，cost = (10+100+100+100+10) − max(MNAS of [100, 100, 100]) = 320 − 200 = 120 ✓

$L = K + 1$ 因為兩端都比較便宜（10），多花一格買端點反而換來中間能省掉更多 100，淨效益是賺的。

L > K + 1 為什麼永遠不必查

要證明：對任何 $L \ge K + 2$，都可以從某一端拿掉一個位置， 得到一個覆蓋長度仍 $\ge K$ 的解，而且 cost 沒變大。

假設最佳解的 $S$ 落在 $[s, e]$，$e - s + 1 \ge K + 2$。 考慮端點 $s$ 跟 $e$：

• 如果端點旁邊（$s+1$ 或 $e-1$）也買了 → 直接拿掉端點，差距還是 1，新解仍合法且少了一筆
• 如果端點旁邊沒買（差距是 2）→ 拿掉端點之後，新端點是 $s+2$ 或 $e-2$，覆蓋長度減少 2，但仍 $\ge K$

兩種情況下都得到不更糟的解。所以最佳解一定可以縮到 $L \in \{K, K+1\}$。

只需要對所有 $[s, e]$ 滿足 $e - s + 1 \in \{K, K+1\}$ 的窗口，計算 cost 取 min。

Step 4：線段樹維護最大不相鄰選和

滑動窗口枚舉 $[s, e]$ 之後，每個窗口要對中間區間 $[s+1, e-1]$ 求 MNAS。 區間查詢 + 點修改（這題其實沒有更新，所以也可以靜態處理；但用線段樹寫法更通用、更好擴充）就是線段樹的標準場景。

節點存什麼

節點上要存的不只是「答案」，還要存「合併兩段時用得到的銜接資訊」。 最大不相鄰選和的銜接資訊是：左端、右端各自有沒有被選。 所以節點需要 4 個值，對應 (左端 e/i) × (右端 e/i) 的 4 種組合：

struct Node {
    long long ee, ei, ie, ii;
    // ee: 左端排除、右端排除 的最大選和
    // ei: 左端排除、右端選入
    // ie: 左端選入、右端排除
    // ii: 左端選入、右端選入
};

葉子節點

單一個位置 $A_i$：

• 左右都「排除」：選和 = 0（什麼也沒選）
• 左右都「選入」：選和 = $A_i$（同一個點當左右端）
• 左排右選 / 左選右排：對單點來說不合法，設 −∞ 表示無效

合併（pushup）

合併左段 L 跟右段 R 時，新節點的 4 個狀態都要列舉左段右端跟右段左端的搭配。關鍵約束：左段右端「選」+ 右段左端「選」是不合法的（兩個相鄰位置都被選）。

// 合併左段 L 跟右段 R
// 新左端 = L 的左端，新右端 = R 的右端
// 中間：L.right ⊕ R.left 不能同時 'i'（兩個都選 = 相鄰違規）

S combine(S L, S R) {
    S r;
    // 新節點左端排除：L 的左端排除
    r.ee = max({L.ee + R.ee, L.ee + R.ie, L.ei + R.ee});
    r.ei = max({L.ee + R.ei, L.ee + R.ii, L.ei + R.ei});
    r.ie = max({L.ie + R.ee, L.ie + R.ie, L.ii + R.ee});
    r.ii = max({L.ie + R.ei, L.ie + R.ii, L.ii + R.ei});
    // 注意：所有 r.* 都「沒有」L.right=i + R.left=i 的組合
    return r;
}

查詢答案

對區間 $[l, r]$ 查 MNAS：合併出來的節點裡取 4 個值的最大值，因為兩端都允許自由選擇。

時間：建樹 $O(N)$、單次區間查詢 $O(\log N)$、共 $O(N \log N)$。

延伸：線段樹「左右端狀態相依」合併模式

這題本質上是線段樹的一個經典模式：節點除了存區間答案，還要存兩端的銜接狀態，pushup 時根據兩段交界處的合法性合併。 這個模式涵蓋了一系列題目，最常見的就是「動態最大連續子陣列和」（Max Subarray Sum with point updates）。

對照例：Max Subarray Sum

這是一個經典題目：給一個數列 $A$，支援單點修改 + 區間查詢區間內的最大子段和。 線段樹節點存 4 個值：

struct Node {
    long long sum;  // 區間總和
    long long ls;   // 區間最大前綴和
    long long rs;   // 區間最大後綴和
    long long mx;   // 區間最大子段和
};

合併邏輯：

void pushup(Node& p, Node L, Node R) {
    p.sum = L.sum + R.sum;
    p.ls  = max(L.ls, L.sum + R.ls);    // 新前綴：留在 L，或跨到 R
    p.rs  = max(R.rs, R.sum + L.rs);    // 新後綴：留在 R，或跨到 L
    p.mx  = max({L.mx, R.mx, L.rs + R.ls});  // 新答案：在 L、在 R、跨界
}

兩種題目的共通結構

兩者的核心都是「分治合併 + 邊界狀態」。 節點不只存答案，還存 boundary info；pushup 時根據合併規則處理交界處。

怎麼判斷一道題該用這套

通常題目滿足下面條件就值得想一想：

• 區間查詢的是某種「最佳化」量（最大子段和、最大不相鄰和、最長連續同色等）
• 合併兩段答案時，跨界的部分需要兩端的局部資訊
• 支援點修改（不然其實 prefix sum / 一次 DP 就夠了）

滿足這三點，幾乎就是線段樹「左右端狀態相依」模式的場景。

完整 Code

#include <bits/stdc++.h>
using namespace std;

const long long NEG_INF = LLONG_MIN / 4;

struct Node {
    long long ee, ei, ie, ii;
};

Node make_leaf(long long a) {
    Node r;
    r.ee = 0;          // 不選
    r.ii = a;          // 選
    r.ei = NEG_INF;    // 單點不能左排右選
    r.ie = NEG_INF;
    return r;
}

Node combine(Node L, Node R) {
    Node r;
    r.ee = max({L.ee + R.ee, L.ee + R.ie, L.ei + R.ee});
    r.ei = max({L.ee + R.ei, L.ee + R.ii, L.ei + R.ei});
    r.ie = max({L.ie + R.ee, L.ie + R.ie, L.ii + R.ee});
    r.ii = max({L.ie + R.ei, L.ie + R.ii, L.ii + R.ei});
    return r;
}

const Node EMPTY = {0, NEG_INF, NEG_INF, NEG_INF};

int n;
vector<Node> seg;
vector<long long> A;

void build(int x, int l, int r) {
    if (l == r) {
        seg[x] = make_leaf(A[l]);
        return;
    }
    int m = (l + r) / 2;
    build(x * 2, l, m);
    build(x * 2 + 1, m + 1, r);
    seg[x] = combine(seg[x * 2], seg[x * 2 + 1]);
}

Node query(int x, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return EMPTY;
    if (ql <= l && r <= qr) return seg[x];
    int m = (l + r) / 2;
    return combine(query(x * 2, l, m, ql, qr),
                   query(x * 2 + 1, m + 1, r, ql, qr));
}

long long mnas(int l, int r) {
    if (l > r) return 0;
    Node q = query(1, 0, n - 1, l, r);
    return max({q.ee, q.ei, q.ie, q.ii});
}

int main() {
    int K;
    cin >> n >> K;
    A.resize(n);
    vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        pref[i + 1] = pref[i] + A[i];
    }
    seg.assign(4 * n, EMPTY);
    build(1, 0, n - 1);

    auto sum_range = [&](int l, int r) {
        return pref[r + 1] - pref[l];
    };

    long long ans = LLONG_MAX;
    for (int L : {K, K + 1}) {
        if (L > n) continue;
        for (int s = 0; s + L - 1 < n; s++) {
            int e = s + L - 1;
            long long total = sum_range(s, e);
            long long save = mnas(s + 1, e - 1);  // 中間最大可省
            ans = min(ans, total - save);
        }
    }
    cout << ans << "\n";
    return 0;
}

Sample 驗證

• Sample 1: $N=5,\ K=2,\ A=[3,1,4,1,5]$ → 答案 2
• Sample 2: $N=6,\ K=4,\ A=[24,3,22,39,4,29]$ → 答案 29

兩個 sample 都會通過。整體複雜度 $O(N \log N)$，$N \le 2 \times 10^5$ 完全夠用。

延伸練習

「線段樹左右端狀態相依」這個模式在 CP 中相當常見，整理一些值得練的題型：

• Max Subarray Sum with point updates：經典題，4 欄節點（sum / ls / rs / mx）
• Max Non-Adjacent Sum with updates：本題、Codeforces 上不少變形題
• 區間最長連續相同字元：節點存 (左端字元、左端長度、右端字元、右端長度、區間答案)
• 區間異或/AND/OR/GCD：合併邏輯較單純（單值傳遞），但仍是同一個分治框架
• 區間最大子段平方和、最大子段乘積：節點要記正最大、負最小，pushup 時取 4 種搭配
• 區間最長同色括號 / 最大合法括號子序列：節點存未匹配左、未匹配右、答案

掌握這個 pattern 之後，不少看起來很難的區間最佳化題其實都是同一套：node 要存什麼 boundary info、pushup 要怎麼合併合法跨界。 把這兩件事想清楚就解一半了。