Overview

This problem asks you to water \(N\) flowers \(M\) times over intervals, and count the number of flowers where the total water received exceeds the required water amount. We use the “difference array (imos method)” to efficiently process range additions.

Analysis

Problems with the Naive Approach

Consider the approach where for each watering task \(j\), we add water amount \(W_j\) to all flowers from position \(L_j\) to \(R_j\).

for each task j:
    for i = L_j to R_j:
        water[i] += W_j

This method requires at most \(O(N)\) operations per watering. With \(M\) tasks, the total becomes \(O(NM)\). When \(N, M \leq 2 \times 10^5\), this requires up to \(4 \times 10^{10}\) operations in the worst case, resulting in TLE (Time Limit Exceeded).

Solution: Difference Array (Imos Method)

We use the “difference array” technique to efficiently handle uniform additions over an interval \([L, R]\).

Basic Idea: - When we want to add value \(W\) to interval \([L, R]\), for the difference array diff: - diff[L] += W (\(+W\) at the start of the interval) - diff[R+1] -= W (\(-W\) at the position after the end of the interval) - Finally, taking the cumulative sum of diff gives the actual value at each position

Concrete Example

For \(N = 5\) flowers, adding water amount \(3\) to interval \([2, 4]\):

Initial: diff = [0, 0, 0, 0, 0, 0]  (size N+1)

Operation: diff[2-1] += 3, diff[4] -= 3
           diff = [0, 3, 0, 0, -3, 0]  (0-indexed)

Taking cumulative sum:
           water = [0, 3, 3, 3, 0, ...]
           → Water amount 3 has been added to flowers 2, 3, 4

Algorithm

1. Initialize a difference array diff of size \(N+1\) with \(0\)s
2. For each watering task \((L_j, R_j, W_j)\):
   • diff[L_j - 1] += W_j (converted to 0-indexed)
   • diff[R_j] -= W_j
3. Calculate the total water water received by each flower \(i\) while taking the cumulative sum of diff
4. Count the number of flowers where water > S[i]

Image of diff array (after 1-indexed → 0-indexed conversion):

Position:  0    1    2    3    4    5   (for N=5)
diff:    [+W]  [ ]  [ ]  [ ] [-W]  [ ]  ← addition to interval [1,4]
          ↓    ↓    ↓    ↓    ↓
Cumsum:   W    W    W    W    0    0    ← actual water amount

Complexity

• Time Complexity: \(O(N + M)\)
  • Additions to difference array: \(O(1)\) per task × \(M\) tasks = \(O(M)\)
  • Cumulative sum calculation and counting: \(O(N)\)
• Space Complexity: \(O(N)\)
  • Size of difference array diff

Implementation Notes

1. Index Conversion: The problem uses 1-indexed notation, but arrays are 0-indexed, so we use L-1 and R (where R is R+1-1, which remains unchanged)

2. Difference Array Size: Since we access diff[R], the size needs to be \(N+1\)

3. Overflow Prevention: The total water amount can reach up to \(M \times 10^9 = 2 \times 10^{14}\), but in Python there’s no need to worry about integer overflow

4. Simultaneous Cumulative Sum and Counting: Instead of creating separate arrays, we can save memory by calculating the cumulative sum and counting within the same loop

Source Code

def main():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    
    # Use difference array to efficiently process range additions
    # diff[i] represents the change in water amount at position i
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L, R, W = map(int, input().split())
        # Since it's 1-indexed, use L-1 and R
        diff[L - 1] += W
        diff[R] -= W
    
    # Take cumulative sum to calculate total water received by each flower
    count = 0
    water = 0
    for i in range(N):
        water += diff[i]
        if water > S[i]:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.