概要

すべての塗装指示を実行したときに塗られる板の集合を考え、そこから「無視した \(K\) 回の指示だけに依存して塗られていた部分」が失われる、と考えます。

各区間ごとに、「この部分を塗っている指示番号の集合」が分かれば、その部分がどの無視区間で失われるかを効率よく求められます。

考察

まず、すべての指示を実行したときに塗られる板の枚数を \(total\) とします。

無視する区間を \(s\) 回目から \(s+K-1\) 回目までとします。

ある板が最終的に塗られなくなるのは、その板を塗っていたすべての指示が、無視した区間 \([s, s+K-1]\) の中に含まれている場合です。

つまり、

• その板を塗っている指示番号の集合を \(A\) とする
• \(A\) の最小値を \(mn\)
• \(A\) の最大値を \(mx\)

とすると、その板が失われる条件は、

\[ s \leq mn \]

かつ

\[ s + K - 1 \geq mx \]

です。

後者は変形すると、

\[ s \geq mx - K + 1 \]

です。

したがって、その板が失われるような \(s\) の範囲は、

\[ mx - K + 1 \leq s \leq mn \]

となります。

ただし、\(s\) は無視区間の開始位置なので、

\[ 1 \leq s \leq M-K+1 \]

も満たす必要があります。

---

素朴に各 \(s\) について、実行される区間の和集合を毎回計算すると、最大で \(O(M^2 \log M)\) 程度かかってしまい、\(M \leq 2 \times 10^5\) では間に合いません。

そこで、板の位置を左から右へ走査しながら、「現在の位置を塗っている指示番号の集合」を管理します。

同じ集合に塗られている連続部分についてはまとめて処理できます。

例えば、ある長さ \(len\) の部分を塗っている指示番号の集合が \(\{3, 5\}\) で、\(K=4\) だとします。

この部分が失われるには、無視する区間が指示 \(3\) と \(5\) の両方を含む必要があります。

長さ \(4\) の連続区間で両方を含む開始位置 \(s\) は、

\[ s \leq 3 \]

かつ

\[ s+3 \geq 5 \]

なので、

\[ 2 \leq s \leq 3 \]

です。

つまり、この長さ \(len\) の部分は、\(s=2,3\) のときだけ失われます。

このように、各連続部分は「失われる \(s\) の範囲」に対してまとめて加算できます。

アルゴリズム

区間 \([L_i, R_i]\) を半開区間 \([L_i, R_i+1)\) として扱います。

各指示について、次のイベントを作ります。

• 座標 \(L_i\) で指示 \(i\) が有効になる
• 座標 \(R_i+1\) で指示 \(i\) が無効になる

これらのイベントを座標順にソートし、左から右へ走査します。

走査中は、現在の区間を塗っている指示番号の集合 active を set で管理します。

隣り合うイベント座標を \(x\), \(nx\) とすると、区間 \([x, nx)\) では active の内容は変化しません。

この長さを

\[ len = nx - x \]

とします。

active が空でなければ、この部分はすべての指示を実行した場合には塗られているので、

\[ total += len \]

とします。

また、この部分が失われる無視開始位置 \(s\) の範囲を求めます。

active に含まれる最小の指示番号を \(mn\)、最大の指示番号を \(mx\) とすると、この部分が失われる条件は、

\[ mx - K + 1 \leq s \leq mn \]

です。

無視開始位置 \(s\) の範囲は、

\[ 1 \leq s \leq W \]

ただし、

\[ W = M - K + 1 \]

なので、実際に加算する範囲は、

\[ l = \max(1, mx - K + 1) \]

\[ r = \min(W, mn) \]

です。

もし \(l \leq r\) なら、この長さ \(len\) は \(s=l,l+1,\dots,r\) のとき失われるので、差分配列で区間加算します。

最後に、各 \(s\) について失われる板の枚数 lost[s] を復元します。

最終的に塗られる板の枚数は、

\[ total - lost[s] \]

なので、これを最大化するには lost[s] を最小化すればよいです。

答えは、

\[ total - \min_s lost[s] \]

です。

計算量

• 時間計算量: \(O(M \log M)\)
• 空間計算量: \(O(M)\)

イベント数は \(2M\) 個です。

イベントのソートに \(O(M \log M)\)、走査中の set への挿入・削除にそれぞれ \(O(\log M)\) かかるため、全体で \(O(M \log M)\) です。

実装のポイント

区間 \([L_i, R_i]\) は両端を含むので、イベントでは \(R_i+1\) を使って半開区間 \([L_i, R_i+1)\) として扱います。

これにより、隣り合うイベント座標 \(x\), \(nx\) の間の長さ \(nx-x\) が、そのまま塗られている板の枚数に対応します。

また、同じ座標に複数のイベントがある場合は、すべて処理してから次の座標までの区間を考える必要があります。

active から現在塗っている指示番号の最小値・最大値を取りたいので、set を使うと、

int mn = *active.begin();
int mx = *active.rbegin();

で取得できます。

板の数 \(N\) は最大 \(10^9\) なので、座標や答えは long long 型で扱います。

ソースコード

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

struct Event {
    long long x;
    int id;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N;
    int M, K;
    cin >> N >> M >> K;

    vector<Event> events;
    events.reserve(2 * M);

    for (int i = 1; i <= M; i++) {
        long long L, R;
        cin >> L >> R;
        events.push_back({L, i});
        events.push_back({R + 1, -i});
    }

    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
        return a.x < b.x;
    });

    int W = M - K + 1;
    vector<long long> diff(W + 3, 0);

    set<int> active;
    long long total = 0;

    size_t p = 0;
    while (p < events.size()) {
        long long x = events[p].x;

        while (p < events.size() && events[p].x == x) {
            int id = events[p].id;
            if (id > 0) active.insert(id);
            else active.erase(-id);
            p++;
        }

        if (p == events.size()) break;

        long long nx = events[p].x;
        long long len = nx - x;

        if (len > 0 && !active.empty()) {
            total += len;

            int mn = *active.begin();
            int mx = *active.rbegin();

            int l = max(1, mx - K + 1);
            int r = min(W, mn);

            if (l <= r) {
                diff[l] += len;
                diff[r + 1] -= len;
            }
        }
    }

    long long cur = 0;
    long long min_lost = LLONG_MAX;

    for (int s = 1; s <= W; s++) {
        cur += diff[s];
        min_lost = min(min_lost, cur);
    }

    cout << total - min_lost << '\n';

    return 0;
}

---

この解説は gpt-5.5-xhigh によって生成されました。