Overview

Given a sequence of \(N\) characters, when an interval of length \(W\) is marked \(K\) times, the problem asks to determine how many times each character is ultimately marked.

Discussion

Naive Approach and Its Limitations

The simplest method is to loop through each marking instruction (from \(L_i\) to \(L_i + W - 1\)) and increment the count one by one. However, this method requires up to \(N\) addition operations per marking. Since marking is performed \(K\) times, the overall time complexity is \(O(NK)\). Looking at the constraints, \(N, K \le 2 \times 10^5\), so \(NK \approx 4 \times 10^{10}\), which will not finish within the time limit (generally, about \(10^8\) operations can be processed per second).

Efficient Solution

To efficiently perform the operation of “adding a value to a specific interval all at once,” we use an algorithm called the “imos method” (difference array technique). Using the imos method, a single range addition can be done with just 2 array operations (\(O(1)\)), and by scanning through the entire array once at the end (\(O(N)\)), we can determine the value at each position.

Algorithm

Steps of the Imos Method

1. Prepare a difference array: Prepare an array diff of size \(N+2\) and initialize all elements to 0.
2. Record the markings: Let the start position of each marking be \(L\) and the end position be \(R = L + W - 1\).
   • Add \(1\) to diff[L] (indicating that a marking starts here)
   • Subtract \(1\) from diff[R + 1] (indicating that the effect of the marking ends here)
3. Compute the prefix sum: Take the prefix sum of the array diff from the beginning. The number of times the \(j\)-th character is marked is given by \(\sum_{i=1}^{j} diff[i]\).

Concrete Example

For \(N=5, W=3, K=1\) with \(L_1=2\): - The marking range is from the 2nd character to the \(2+3-1=4\)th character. - diff[2] += 1 - diff[4 + 1] -= 1 - State of the diff array: [0, 0, 1, 0, 0, -1] - Taking the prefix sum: 0, 0, 1, 1, 1, 0 - Count for each character: 0 1 1 1 0, which is correctly computed.

Complexity

• Time complexity: \(O(N + K)\)
  • Recording the \(K\) markings takes \(O(K)\), and the final prefix sum computation takes \(O(N)\). This is sufficiently fast under the given constraints.
• Space complexity: \(O(N)\)
  • An array of roughly length \(N\) is needed for storing differences and for output.

Implementation Notes

• Fast I/O: In Python, when \(N\) or \(K\) is large, repeatedly calling input() or print() can become an I/O bottleneck. You can speed things up by reading all input at once with sys.stdin.read().split() or by using sys.stdout.write().

• Array size: Since we access the index \(R+1\) (i.e., \(L+W\)), the array size should be slightly larger than \(N+1\) (e.g., \(N+2\)) to prevent out-of-bounds errors.

  Source Code

import sys

def main():
    # 高速な入出力のために、すべての入力を一度に読み込んで空白で分割します。
    # N: 文字の総数, W: 蛍光ペンの幅, K: マーキングの回数
    data = sys.stdin.read().split()
    
    if not data:
        return
    
    # 最初の3つの要素が N, W, K です。
    n = int(data[0])
    w = int(data[1])
    k = int(data[2])
    
    # いもす法（累積和の応用）のための差分配列を用意します。
    # 1-indexed で管理するため、サイズを N + 2 とします。
    # diff[i] は i 文字目のマーキング回数の変化量を表します。
    diff = [0] * (n + 2)
    
    # 各マーキングの開始位置 L_i は data[3] 以降に格納されています。
    # マーキングされる範囲は [L_i, L_i + W - 1] です。
    for i in range(3, 3 + k):
        l = int(data[i])
        # 範囲の開始位置でカウントを増やします。
        diff[l] += 1
        # 範囲の終了位置の直後（L_i + W）でカウントを減らします。
        # 制約 L_i <= N - W + 1 により、L_i + W は最大で N + 1 となります。
        if l + w <= n + 1:
            diff[l + w] -= 1
            
    # 差分配列の累積和を計算して、各文字が何回マーキングされたかを求めます。
    results = [0] * n
    current_count = 0
    for j in range(1, n + 1):
        current_count += diff[j]
        results[j - 1] = current_count
        
    # 結果をスペース区切りの文字列として結合し、一括で出力します。
    sys.stdout.write(" ".join(map(str, results)) + "\n")

if __name__ == "__main__":
    main()

This editorial was generated by gemini-3-flash-preview.