This problem is taken from the 2021 International Olympiad of Informatics:

# Problem

Aunty Khong is preparing n boxes of candies for students from a nearby school. The boxes are

numbered from 0 to n − 1 and are initially empty. Box

i\ (0 ≤ i ≤ n − 1) has a capacity of c[i]

candies.

Aunty Khong spends q days preparing the boxes. On day j\ ( 0 ≤ j ≤ q − 1), she performs an

action specified by three integers l[j], r[j] and v[j] where 0 ≤ l[j] ≤ r[j] ≤ n − 1 and

v[j] ≠ 0. For each box k satisfying l[j] ≤ k ≤ r[j]:

If v[j] > 0, Aunty Khong adds candies to box k, one by one, until she has added exactly v[j]

candies or the box becomes full. In other words, if the box had p candies before the action, it

will have min(c[k], p + v[j]) candies after the action.

If v[j] < 0, Aunty Khong removes candies from box k, one by one, until she has removed

exactly −v[j] candies or the box becomes empty. In other words, if the box had p candies

before the action, it will have max(0, p + v[j]) candies after the action.

Your task is to determine the number of candies in each box after the q days.

# Example

Consider

```
c = [10, 15, 13]
l = [0, 0]
r = [2, 1]
v = [20, -11]
```

This means that box 0 has a capacity of 10 candies, box 1 has a capacity of 15 candies, and box 2

has a capacity of 13 candies.

At the end of day 0, box 0 has min(c[0], 0 + v[0]) = 10 candies, box 1 has

min(c[1], 0 + v[0]) = 15 candies and box 2 has min(c[2], 0 + v[0]) = 13 candies.

At the end of day 1, box 0 has max(0, 10 + v[1]) = 0 candies, box 1 has

max(0, 15 + v[1]) = 4 candies. Since 2 > r[1], there is no change in the number of candies in

box 2. The number of candies at the end of each day are summarized below:

Day | Box 0 | Box 1 | Box 2 |
---|---|---|---|

0 | 10 | 15 | 13 |

1 | 0 | 4 | 13 |

# Constraints

1 ≤ n ≤ 200 000

1 ≤ q ≤ 200 000

1 ≤ c[i] ≤ 10\ (for\ all\ 0 ≤ i ≤ n − 1)

0 ≤ l[j] ≤ r[j] ≤ n − 1\ (for\ all\ 0 ≤ j ≤ q − 1)

−10 ≤ v[j] ≤ 10 , v[j] ≠ 0\ (for\ all\ 0 ≤ j ≤ q − 1)

# Initial Approaches

## Naive Approach

For each query, update each container - this is too slow.

## Online Queries

Use a data structure with O(\log(n)) complexity to update your data structure for each query.

## Offline Queries

Transform the queries into a more useful form than a list.

For each i\ (0 ≤ i ≤ n − 1), calculate the value of c[i] after q queries.

# Further Ideas

Consider that we have one container of capacity c. Store all the queries as they happen in two prefix sums. In the first one, a[0] = 0, a[i+1] = min(a[i]+v[i],0) and in the second, b[0] = 0, b[i+1] = max(b[i]+v[i],0). This means we will be able to discard a[i] and b[i]\ (0 ≤ j ≤ i), b[i] = 0 or a[i] = 0.

We can also discard a[i] and b[i]\ (0 ≤ j ≤ i), b[i] ≤ -c or a[i] \ge c, which means that we just look at the final part of the array, which is already a prefix sum.

## Issues

- I don’t know how to implement the above code for multiple values of c.
- I don’t know how to answer queries in \log(q) or \log(n) time

Any help would be greatly appreciated.