Count the Deliveries

Subtask 1:

For first task, we can just simulate the records (since only one customer’s order changes and only one customer orders during a record).

Subtask 2:

In second subtask, we can keep the orders in a segment tree. For each customer we track how many orders he has performed. Then, when his order amount changes, we use the previous order amount and the kept order count to calculate total deliveries and reset the order count to 0 so that the previous order count do not affect new order amount.

Subtask 3:

For subtask 3, we will also use segment tree, but this segment tree will keep weight and value for each index. And a query on a range will return the sum of all weight $\times$ value in that range. Initially, we will read all records then compute the answers for each customer. To do this, we will keep a $q$ size segment tree. If i-th record increases $l-r$ customers’ amount by $x$, then, before computing l-th customer’s answer, we’ll increase value of index $i$ by $x$, and before computing $r+1$-th customer’s answer we will decrease value of index $i$ by $x$. And if j-th record is l-r customers ordering $x$ times then, before computing $l$-th customer’s answer we will increase weight of indices $1$ to $j$ by $x$ and before computing $r+1$-th customer’s answer we will decrease weight of indices $1$ to $j$ by $x$. Then to compute answer for a customer we only need to get sum of weight $\times$ value of all indices.