Overview

A problem where we process queries that uniformly add values to intervals and determine the final value of each element. This can be solved efficiently using the Imos method (prefix sum preprocessing).

Analysis

In this problem, for each of the \(K\) operations, we need to perform a “+1 to all characters in a certain contiguous interval” operation. For example, if \(N = 5\), \(W = 3\), and the marking start position is \(L = 1\), then characters 1 through 3 get +1.

As a naive approach, if we consider actually updating each element of the interval for every operation, each operation requires updating up to \(W\) elements, and in total we would need up to \(K \times W\) updates. Given the constraints, this can be up to \(2 \times 10^{10}\), which cannot be processed within the time limit (TLE).

This is where the Imos method comes in. This is a technique for efficiently performing uniform addition over intervals, utilizing a difference array.

Specifically: - The operation of adding value \(x\) to interval \([l, r)\) can be represented by adding \(+x\) to the \(l\)-th position and \(-x\) to the \(r\)-th position of the difference array. - By taking the prefix sum at the end, we obtain the actual value of each element.

In this problem, since we add +1 to the interval \([L_i, L_i + W)\), we set diff[L_i - 1] += 1 and diff[L_i + W - 1] -= 1 (note the 0-indexed conversion). Then, by taking the prefix sum, we can obtain the marking count for each character.

Algorithm

1. Prepare a difference array diff of length \(N+1\) (one extra for boundary handling).
2. For each marking, determine the start position \(L_i\) and end position \(L_i + W - 1\), then:
   • diff[L_i - 1] += 1
   • diff[L_i + W - 1] -= 1
3. Compute the prefix sum of diff to obtain the marking count for each character.
4. Output the first \(N\) elements.

Example

Sample input:

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

That is, add +1 to intervals [1,3] and [3,5].

Changes to the difference array: - Initial state: [0, 0, 0, 0, 0, 0] - 1st operation: diff[0] += 1, diff[3] -= 1 → [1, 0, 0, -1, 0, 0] - 2nd operation: diff[2] += 1, diff[5] -= 1 → [1, 0, 1, -1, 0, -1]

Taking the prefix sum: - [1, 1, 2, 1, 1]

This is the answer.

Complexity

• Time complexity: \(O(N + K)\)
• Space complexity: \(O(N)\)

Each operation finishes in constant time, and we take the prefix sum only once at the end, so the entire process runs in linear time.

Implementation Notes

• Making the difference array length \(N+1\) ensures safe handling of the subtraction at the end boundary.

• Since indices are handled as 0-based, start position \(L_i\) is treated as \(L_i - 1\) in the code.

• For the final prefix sum, we need to extract only the first \(N\) elements.

  Source Code

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()

---

This editorial was generated by qwen3-coder-480b.