概要

\(N\) 枚の板に対して \(M\) 回の区間塗装指示が出されます。このうち連続する \(K\) 回の指示を無視したとき、最終的に塗装されている板の枚数を最大化する問題です。板の総数 \(N\) が非常に大きいため、座標圧縮と効率的な区間管理が鍵となります。

考察

1. 座標圧縮の必要性

板の枚数 \(N\) は最大 \(10^9\) と非常に大きいため、板を 1 枚ずつ管理することは不可能です。一方で、指示の数 \(M\) は \(2 \times 10^5\) と比較的小さいため、指示の端点（\(L_i\) と \(R_i+1\)）に注目する座標圧縮を用いることで、管理すべき区間の数を \(O(M)\) の規模に抑えることができます。

2. 板が「未塗装」になる条件

ある区間が最終的に「未塗装」になるのは、「その区間を塗るはずだったすべての指示が、無視する \(K\) 回の中に含まれている」ときだけです。

各圧縮後の区間について、それをカバーする指示のインデックスの集合を \(I\) とします。無視する指示の範囲を \([s, s+K-1]\) とすると、その区間が未塗装になる条件は以下の通りです： - \(I\) に含まれる最小のインデックスを \(\min(I)\)、最大のインデックスを \(\max(I)\) としたとき、 - \(s \leq \min(I)\) かつ \(\max(I) \leq s+K-1\)

これを \(s\) について整理すると、以下のようになります： - \(\max(I) - K + 1 \leq s \leq \min(I)\)

この条件を満たす \(s\) の範囲において、その区間の長さ分だけ「塗装される板の総数」が減少することになります。

3. 各区間の最小・最大インデックスの取得

各区間をカバーする指示の最小・最大インデックスを効率よく求める必要があります。これは、セグメント木を用いた区間更新（Range Chmin / Range Chmax）を行うことで、各リーフ（最小単位の区間）に対して \(O(\log M)\) または一括処理で求めることができます。

アルゴリズム

1. 座標圧縮: すべての指示の左端 \(L_i\) と右端の次 \(R_i+1\) を集めてソートし、重複を除きます。これにより、数直線が最大 \(2M-1\) 個の小区間に分割されます。
2. 区間情報の収集: セグメント木（または遅延評価付きの構造）を準備し、各指示 \(i\) について、それがカバーする小区間に対して「インデックス \(i\)」で更新を行います。
   • tree_min: その区間を覆う最小のインデックスを保持
   • tree_max: その区間を覆う最大のインデックスを保持
3. 減少量の計算: 各小区間について、もし一度でも塗られるなら（\(\min(I) \neq \infty\)）：
   • 条件 \(\max(I) - K + 1 \leq s \leq \min(I)\) を満たす \(s\) の範囲を求めます。
   • この \(s\) の範囲に対して、その区間の長さ分だけ「塗装枚数の減少量」を加算します。これはいもす法（差分配列）を用いることで効率的に行えます。
4. 最適解の選択: 全指示を実行した場合の塗装枚数の合計から、いもす法で計算した「減少量」の最小値を引いたものが答えとなります。

計算量

• 時間計算量: \(O(M \log M)\)
  • 座標圧縮のためのソート: \(O(M \log M)\)
  • セグメント木への \(M\) 回の区間更新: \(O(M \log M)\)
  • いもす法による集計: \(O(M)\)
• 空間計算量: \(O(M)\)
  • 座標圧縮後の配列、セグメント木、差分配列などで \(O(M)\) のメモリを使用します。

実装のポイント

• 半開区間の利用: 板 \(L_i\) から \(R_i\) までを塗るという指示を、座標圧縮上では \([L_i, R_i+1)\) という半開区間として扱うと、区間の長さの計算（\(coords[j+1] - coords[j]\)）が簡潔になります。

• セグメント木の簡略化: 今回は「最後に各リーフの値が分かれば良い」ため、完全な遅延伝搬セグメント木を実装しなくても、各ノードに値を保持しておき、最後に根から葉へ値を伝搬させる（push_down）だけで十分です。

• \(s\) の範囲: 無視する開始位置 \(s\) は \(1 \leq s \leq M-K+1\) の範囲を動くことに注意してください。助変数 \(s\) の範囲外にならないよう max(1, ...) や min(M-K+1, ...) でクランプする必要があります。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Problem: Fence Painting
 * We need to maximize the number of painted boards after ignoring exactly K consecutive instructions.
 * N can be up to 10^9, so coordinate compression is necessary.
 * M is up to 2 * 10^5, which allows for O(M log M) solutions.
 */

const int INF = 1e9 + 7;

int main() {
    // Optimize input and output
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long N;
    int M, K;
    if (!(cin >> N >> M >> K)) return 0;

    // Store instructions and collect all relevant coordinates for compression
    vector<pair<int, int>> instructions(M);
    vector<int> coords;
    coords.reserve(2 * M);
    for (int i = 0; i < M; ++i) {
        cin >> instructions[i].first >> instructions[i].second;
        // The instructions cover boards from L_i to R_i inclusive.
        // This corresponds to the interval [L_i, R_i + 1) in coordinate space.
        coords.push_back(instructions[i].first);
        coords.push_back(instructions[i].second + 1);
    }

    // Coordinate compression
    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());

    int P = (int)coords.size();
    int num_intervals = P - 1;

    // If there are no intervals, no boards are painted.
    if (num_intervals <= 0) {
        cout << 0 << endl;
        return 0;
    }

    // Segment trees to store the minimum and maximum instruction index covering each interval.
    // We only need the final leaf values after all updates, so we can push down lazy updates at the end.
    vector<int> tree_min(4 * num_intervals, INF);
    vector<int> tree_max(4 * num_intervals, -INF);

    // Range update function for segment tree (minimum)
    auto update_min = [&](auto self, int node, int start, int end, int l, int r, int val) -> void {
        if (start > end || start > r || end < l) return;
        if (start >= l && end <= r) {
            tree_min[node] = min(tree_min[node], val);
            return;
        }
        int mid = start + (end - start) / 2;
        self(self, 2 * node, start, mid, l, r, val);
        self(self, 2 * node + 1, mid + 1, end, l, r, val);
    };

    // Range update function for segment tree (maximum)
    auto update_max = [&](auto self, int node, int start, int end, int l, int r, int val) -> void {
        if (start > end || start > r || end < l) return;
        if (start >= l && end <= r) {
            tree_max[node] = max(tree_max[node], val);
            return;
        }
        int mid = start + (end - start) / 2;
        self(self, 2 * node, start, mid, l, r, val);
        self(self, 2 * node + 1, mid + 1, end, l, r, val);
    };

    // Process each instruction and update the range of intervals it covers.
    for (int i = 0; i < M; ++i) {
        int l_idx = lower_bound(coords.begin(), coords.end(), instructions[i].first) - coords.begin();
        int r_idx = lower_bound(coords.begin(), coords.end(), instructions[i].second + 1) - coords.begin() - 1;
        if (l_idx <= r_idx) {
            update_min(update_min, 1, 0, num_intervals - 1, l_idx, r_idx, i + 1);
            update_max(update_max, 1, 0, num_intervals - 1, l_idx, r_idx, i + 1);
        }
    }

    // Leaf arrays to store the final min and max index for each interval.
    vector<int> min_idx_leaf(num_intervals, INF);
    vector<int> max_idx_leaf(num_intervals, -INF);

    // Push down the updates from the segment tree to the leaves.
    auto push_down = [&](auto self, int node, int start, int end, int cur_min, int cur_max) -> void {
        cur_min = min(cur_min, tree_min[node]);
        cur_max = max(cur_max, tree_max[node]);
        if (start == end) {
            min_idx_leaf[start] = cur_min;
            max_idx_leaf[start] = cur_max;
            return;
        }
        int mid = start + (end - start) / 2;
        self(self, 2 * node, start, mid, cur_min, cur_max);
        self(self, 2 * node + 1, mid + 1, end, cur_min, cur_max);
    };

    push_down(push_down, 1, 0, num_intervals - 1, INF, -INF);

    long long total_painted = 0;
    // Difference array to calculate the reduction in painted area for each possible window s.
    vector<long long> reduction_diff(M + 2, 0);

    for (int j = 0; j < num_intervals; ++j) {
        if (min_idx_leaf[j] != INF) {
            long long width = (long long)coords[j + 1] - coords[j];
            total_painted += width;
            
            // An interval becomes unpainted if ALL instructions covering it are ignored.
            // This happens if the ignored window [s, s + K - 1] contains both the 
            // minimum and maximum instruction indices that cover the interval.
            int l_s = max(1, max_idx_leaf[j] - K + 1);
            int r_s = min(M - K + 1, min_idx_leaf[j]);
            
            if (l_s <= r_s) {
                reduction_diff[l_s] += width;
                reduction_diff[r_s + 1] -= width;
            }
        }
    }

    // Find the window s that results in the minimum reduction of painted boards.
    long long min_reduction = -1;
    long long current_reduction = 0;
    for (int s = 1; s <= M - K + 1; ++s) {
        current_reduction += reduction_diff[s];
        if (min_reduction == -1 || current_reduction < min_reduction) {
            min_reduction = current_reduction;
        }
    }

    // If no window was processed, reduction is 0.
    if (min_reduction == -1) min_reduction = 0;

    // The maximum number of painted boards is the initial total minus the minimum reduction.
    cout << total_painted - min_reduction << endl;

    return 0;
}

---

この解説は gemini-3-flash-thinking によって生成されました。