概要

すべての塗装指示を実行した場合に塗られる板の枚数から、「無視したことで塗られなくなる板の枚数」を引いて考えます。
各板について、その板を塗る指示番号の集合が、無視する連続 \(K\) 回の中にすべて含まれるときだけ、その板は失われます。

考察

板 \(x\) を塗る指示番号の集合を \(S_x\) とします。

無視する区間を \([s, s+K-1]\) としたとき、板 \(x\) が最終的に塗られないのは次の場合です。

• もともとは少なくとも 1 回塗られる
• その板を塗るすべての指示が、無視する区間 \([s, s+K-1]\) に含まれる

つまり、

\[ S_x \subseteq [s, s+K-1] \]

であるときだけ、板 \(x\) は「失われる」ことになります。

したがって、答えは

\[ \text{全指示を実行したときに塗られる板の枚数} - \text{失われる板の枚数の最小値} \]

です。

---

素朴に各 \(s\) について実行する指示を集めて区間の union を計算すると、\(s\) は最大 \(M\) 通りあり、各回に \(O(M \log M)\) かかるため、全体で \(O(M^2 \log M)\) となり間に合いません。

また、\(N\) は最大 \(10^9\) なので、板を 1 枚ずつ見ることもできません。

そこで、塗装区間の端点だけに注目します。
区間の端点の間では、「現在その場所を塗っている指示の集合」は変化しません。

例えば、ある連続した板の範囲で有効な指示集合が

\[ S = \{2, 5, 6\} \]

だったとします。

この範囲が失われるには、無視する区間 \([s, s+K-1]\) が \(2,5,6\) をすべて含む必要があります。
つまり、最小の指示番号と最大の指示番号だけを見れば十分です。

\[ \min S = 2,\quad \max S = 6 \]

なので、条件は

\[ s \leq 2 \]

かつ

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

です。

変形すると、

\[ 6-K+1 \leq s \leq 2 \]

となります。

一般に、現在の有効な指示集合を \(S\)、その最小値を \(\mathrm{mn}\)、最大値を \(\mathrm{mx}\) とすると、その範囲が失われる \(s\) は

\[ \mathrm{mx}-K+1 \leq s \leq \mathrm{mn} \]

を満たすものです。

ただし、\(s\) は

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

でなければならないので、実際には

\[ \max(1, \mathrm{mx}-K+1) \leq s \leq \min(\mathrm{mn}, M-K+1) \]

です。

この範囲のすべての \(s\) に対して、「この板の範囲の長さ」だけ失われる枚数を加算すればよいです。

アルゴリズム

まず、各塗装指示 \([L_i, R_i]\) を半開区間として扱います。

\[ [L_i, R_i+1) \]

とすることで、長さをそのまま

\[ R_i+1-L_i \]

として扱えます。

各指示について、以下の 2 種類のイベントを作ります。

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

これらのイベントを座標順に処理します。

---

掃き出し中、現在有効な指示番号集合 \(S\) について、以下を高速に取得したいです。

• 最小の指示番号 \(\mathrm{mn}\)
• 最大の指示番号 \(\mathrm{mx}\)

そのために、2 つのヒープを使います。

• 最小値取得用の min-heap
• 最大値取得用の max-heap

Python では max-heap がないので、負の値を入れて管理します。

削除については、ヒープから直接削除するのは難しいため、alive[i] で指示 \(i\) が現在有効かどうかを管理し、ヒープの先頭が無効な指示なら取り除く、という遅延削除を行います。

---

ある座標 \(x\) のイベントをすべて処理した後、次のイベント座標を \(nx\) とします。

このとき、区間

\[ [x, nx) \]

では有効な指示集合は変化しません。

長さは

\[ nx-x \]

です。

有効な指示が 1 つ以上あるなら、この範囲は全指示を実行した場合には塗られるので、total に長さを加えます。

さらに、この範囲が失われる無視区間の開始位置 \(s\) を求めます。

現在有効な指示番号の最小値を \(\mathrm{mn}\)、最大値を \(\mathrm{mx}\) とすると、この範囲が失われる条件は

\[ [s, s+K-1] \supseteq [\mathrm{mn}, \mathrm{mx}] \]

です。

したがって、

\[ \mathrm{mx}-K+1 \leq s \leq \mathrm{mn} \]

です。

実際に選べる \(s\) は

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

なので、加算する範囲は

\[ \max(1, \mathrm{mx}-K+1) \]

から

\[ \min(\mathrm{mn}, M-K+1) \]

までです。

この範囲に現在の長さを加算します。

範囲加算を高速に行うため、imos 法を使います。
diff[l] += length, diff[r+1] -= length としておき、最後に累積和を取ることで各 \(s\) に対する失われる枚数が分かります。

最後に、失われる枚数の最小値を min_loss として、

\[ \text{答え} = \text{total} - \text{min_loss} \]

を出力します。

計算量

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

イベント数は各指示につき 2 個なので \(2M\) 個です。
イベントのソートに \(O(M \log M)\)、掃き出し中のヒープ操作も全体で \(O(M \log M)\) です。

実装のポイント

半開区間 \([L_i, R_i+1)\) として扱うことで、連続した板の枚数を単純に座標差で計算できます。

events[p] = (l << shift) | i
events[p] = ((r + 1) << shift) | (M + i)

コードではイベントをタプルではなく整数に詰めて管理しています。
これは高速化のためで、意味としては次のようなイベントを持っているのと同じです。

• (座標, 指示番号) : 追加イベント
• (座標, M + 指示番号) : 削除イベント

また、同じ座標にあるイベントはすべてまとめて処理します。
その後、次のイベント座標までの区間について、有効な指示集合が一定であるとして処理します。

ヒープでは削除済みの指示が残ることがあるので、先頭が無効なら取り除きます。

while min_heap and not alive[min_heap[0]]:
    heappop(min_heap)

while max_heap and not alive[-max_heap[0]]:
    heappop(max_heap)

これにより、現在有効な指示番号の最小値と最大値を正しく取得できます。

ソースコード

import sys
import heapq

def main():
    input = sys.stdin.buffer.readline
    N, M, K = map(int, input().split())

    shift = (2 * M + 1).bit_length()
    mask = (1 << shift) - 1

    events = [0] * (2 * M)
    p = 0
    for i in range(1, M + 1):
        l, r = map(int, input().split())
        events[p] = (l << shift) | i
        p += 1
        events[p] = ((r + 1) << shift) | (M + i)
        p += 1

    events.sort()

    s_count = M - K + 1
    diff = [0] * (s_count + 2)

    alive = bytearray(M + 1)
    min_heap = []
    max_heap = []
    heappush = heapq.heappush
    heappop = heapq.heappop

    total = 0
    i = 0
    e_len = 2 * M

    while i < e_len:
        x = events[i] >> shift

        while i < e_len and (events[i] >> shift) == x:
            code = events[i] & mask
            if code <= M:
                idx = code
                alive[idx] = 1
                heappush(min_heap, idx)
                heappush(max_heap, -idx)
            else:
                idx = code - M
                alive[idx] = 0
            i += 1

        while min_heap and not alive[min_heap[0]]:
            heappop(min_heap)
        while max_heap and not alive[-max_heap[0]]:
            heappop(max_heap)

        if i < e_len and min_heap:
            length = (events[i] >> shift) - x
            total += length

            mn = min_heap[0]
            mx = -max_heap[0]

            if mx - mn < K:
                left = mx - K + 1
                if left < 1:
                    left = 1
                right = mn
                if right > s_count:
                    right = s_count

                if left <= right:
                    diff[left] += length
                    diff[right + 1] -= length

    cur = 0
    min_loss = 10**30
    for s in range(1, s_count + 1):
        cur += diff[s]
        if cur < min_loss:
            min_loss = cur

    print(total - min_loss)

if __name__ == "__main__":
    main()

---

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