概要

長さ \(N\) の文字列に対して、長さ \(W\) の区間を \(K\) 回マーキングしたとき、各位置が合計何回マーキングされたかを求めます。

考察

各マーキングは区間 \([L_i,\;L_i+W-1]\)（連続 \(W\) 文字）を一度に +1 する操作です。

素朴に「毎回その区間の \(W\) 個を全部 +1」すると、計算量は \(O(KW)\) になります。制約では \(N, K \le 2\times 10^5\) なので、例えば \(W\) も大きいと最大で \(4\times 10^{10}\) 回程度の更新になり、時間内に終わりません（TLE）。

そこで重要な気づきは、「区間をまとめて加算する操作は、差分配列（いもす法）で高速に処理できる」ということです。
区間全体に +1 する代わりに、

• 区間の開始位置に +1
• 区間の終了位置の 次 に -1

という“境界だけ”を記録しておき、最後に累積和を取れば各位置の値を復元できます。

アルゴリズム

差分配列 diff を用意し、最終的な回数配列 a を以下で求めます（ここでは添字を 1-indexed で考える）。

• マーキング区間は \([L,\;L+W-1]\)
• 終了位置の次は \((L+W)\)

各操作について

1. diff[L] += 1
2. diff[L+W] -= 1（ただし \(L+W \le N\) のときのみ。\(N\) より外は累積和を取らないので不要）

その後、\(i=1\) から \(N\) まで累積和を取り、

• cur += diff[i]
• a[i] = cur

とすれば a[i] が「文字 \(i\) がマーキングされた回数」になります。

具体例

\(N=7,\;W=3\) で \(L=2\) を 1 回行うと区間は \([2,4]\)。
差分更新は diff[2]+=1, diff[5]-=1。
累積和を取ると、位置 2〜4 だけが 1 になり、他は 0 のままになります。

計算量

• 時間計算量: \(O(N+K)\)（差分更新が \(K\) 回、累積和が \(N\) 回）
• 空間計算量: \(O(N)\)（差分配列と答え配列）

実装のポイント

• 区間 \([L,\;L+W-1]\) の「終了の次」は \(L+W\) になる点に注意します（\(+W-1\) ではない）。

• diff は 1〜\(N\) を使うので、余裕を持って長さ N+2 を確保しておくと安全です。

• 入力が最大 \(2\times 10^5\) 行あるため、sys.stdin.buffer.read() でまとめて読むと高速です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, W, K = data[0], data[1], data[2]
    Ls = data[3:3+K]

    diff = [0] * (N + 2)  # 1..N, use N+1 for subtraction
    for L in Ls:
        diff[L] += 1
        end = L + W
        if end <= N:
            diff[end] -= 1

    ans = [0] * N
    cur = 0
    for i in range(1, N + 1):
        cur += diff[i]
        ans[i - 1] = cur

    sys.stdout.write(" ".join(map(str, ans)))

if __name__ == "__main__":
    main()

---

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