Overview

Given a string of length \(N\), we mark intervals of length \(W\) a total of \(K\) times, and we need to determine how many times each position has been marked in total.

Analysis

Each marking operation adds +1 to the entire interval \([L_i,\;L_i+W-1]\) (a contiguous segment of \(W\) characters).

A naive approach of “incrementing all \(W\) positions in the interval each time” results in \(O(KW)\) time complexity. Given the constraints \(N, K \le 2\times 10^5\), if \(W\) is also large, this could require up to around \(4\times 10^{10}\) updates, which will not finish in time (TLE).

The key insight here is that “range addition operations can be efficiently processed using a difference array (imos method).” Instead of adding +1 to every position in the interval, we simply record the “boundaries”:

• Add +1 at the start of the interval
• Add -1 at the position immediately after the end of the interval

Then, by taking the prefix sum at the end, we can recover the value at each position.

Algorithm

Prepare a difference array diff and compute the final count array a as follows (using 1-indexed notation here).

• The marking interval is \([L,\;L+W-1]\)
• The position immediately after the end is \((L+W)\)

For each operation:

1. diff[L] += 1
2. diff[L+W] -= 1 (only when \(L+W \le N\); positions beyond \(N\) are unnecessary since we don’t compute the prefix sum there)

Then, take the prefix sum from \(i=1\) to \(N\):

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

This gives a[i] as “the number of times character \(i\) has been marked.”

Concrete Example

With \(N=7,\;W=3\) and performing \(L=2\) once, the interval is \([2,4]\). The difference array update is diff[2]+=1, diff[5]-=1. Taking the prefix sum results in positions 2 through 4 having a value of 1, while all other positions remain 0.

Time Complexity

• Time complexity: \(O(N+K)\) (\(K\) difference array updates and \(N\) prefix sum computations)
• Space complexity: \(O(N)\) (difference array and answer array)

Implementation Notes

• Note that the “position after the end” of the interval \([L,\;L+W-1]\) is \(L+W\) (not \(+W-1\)).

• Since diff uses indices 1 through \(N\), it is safe to allocate it with length N+2 to have some margin.

• Since the input can have up to \(2\times 10^5\) lines, reading it all at once with sys.stdin.buffer.read() is faster.

  Source Code

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

---

This editorial was generated by gpt-5.2-high.