概要

各区間に一様に値を加算するクエリを処理し、最終的な各要素の値を求める問題。いもす法（累積和の前処理）を用いることで効率的に解ける。

考察

この問題では、\(K\) 回の操作それぞれで「ある連続区間の文字すべてに対して +1 する」処理を行う必要があります。
例えば、\(N = 5\), \(W = 3\), マーキング開始位置が \(L = 1\) の場合、「文字1〜3」に +1 されます。

素朴な方法として、各操作ごとに実際に区間の各要素を更新することを考えると、
1回の操作で最大 \(W\) 要素を更新する必要があり、全体で最大 \(K \times W\) 回の更新が必要になります。
制約より、これは最大 \(2 \times 10^{10}\) となり、時間内に処理できません（TLE）。

そこで登場するのが いもす法（Imos method）です。
これは、区間への一様加算を高速に行うためのテクニックで、差分配列（difference array）を利用します。

具体的には： - 区間 \([l, r)\) に値 \(x\) を加える操作は、差分配列の \(l\) 番目に \(+x\)、\(r\) 番目に \(-x\) を加えることで表現できます。 - 最後に累積和を取ることで、各要素の実際の値が得られます。

今回の問題では、区間 \([L_i, L_i + W)\) に +1 を加えるので、
差分配列の diff[L_i - 1] += 1、diff[L_i + W - 1] -= 1 とすればよいです（0-indexedに注意）。
その後、累積和を取ることで各文字のマーキング回数を得ることができます。

アルゴリズム

1. 長さ \(N+1\) の差分配列 diff を用意する（最後の境界処理のため1つ多く取る）。
2. 各マーキングについて、開始位置 \(L_i\) と終了位置 \(L_i + W - 1\) を求め、
   • diff[L_i - 1] += 1
   • diff[L_i + W - 1] -= 1 を行う。
3. diff の累積和を計算することで、各文字のマーキング回数を得る。
4. 最初の \(N\) 要素を出力する。

例

入力例：

N=5, W=3, K=2
L = [1, 3]

つまり、区間 [1,3] と [3,5] に +1 する。

差分配列の変化： - 初期状態: [0, 0, 0, 0, 0, 0] - 1回目: diff[0] += 1, diff[3] -= 1 → [1, 0, 0, -1, 0, 0] - 2回目: diff[2] += 1, diff[5] -= 1 → [1, 0, 1, -1, 0, -1]

累積和を取ると： - [1, 1, 2, 1, 1]

これが答えになります。

計算量

• 時間計算量: \(O(N + K)\)
• 空間計算量: \(O(N)\)

各操作が定数時間で終わり、最後に1回だけ累積和を取るので、全体で線形時間で処理可能です。

実装のポイント

• 差分配列は長さ \(N+1\) にしておくと、終端の減算処理が安全に行える。
• インデックスは0-basedで扱うため、開始位置 \(L_i\) はコード上で \(L_i - 1\) として扱う。
• 最後の累積和は最初の \(N\) 要素までを取り出す必要がある。

## ソースコード

```python
import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    W = int(data[1])
    K = int(data[2])
    
    # 差分配列を初期化
    diff = [0] * (N + 1)
    
    # 各マーキング操作を差分配列に反映
    for i in range(K):
        L = int(data[3 + i])
        diff[L - 1] += 1
        diff[L + W - 1] -= 1
    
    # 累積和を計算して各文字のマーキング回数を求める
    marking_counts = list(accumulate(diff))[:N]
    
    # 結果を出力
    print(' '.join(map(str, marking_counts)))

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。