Putting Boxes Together
Contest: Technocup 2019 - Elimination Round 1
Difficulty rating: 2500
Tags: data structures

There is an infinite line consisting of cells. There are $$$n$$$ boxes in some cells of this line. The $$$i$$$-th box stands in the cell $$$a_i$$$ and has weight $$$w_i$$$. All $$$a_i$$$ are distinct, moreover, $$$a_{i - 1} < a_i$$$ holds for all valid $$$i$$$.

You would like to put together some boxes. Putting together boxes with indices in the segment $$$[l, r]$$$ means that you will move some of them in such a way that their positions will form some segment $$$[x, x + (r - l)]$$$.

In one step you can move any box to a neighboring cell if it isn't occupied by another box (i.e. you can choose $$$i$$$ and change $$$a_i$$$ by $$$1$$$, all positions should remain distinct). You spend $$$w_i$$$ units of energy moving the box $$$i$$$ by one cell. You can move any box any number of times, in arbitrary order.

Sometimes weights of some boxes change, so you have queries of two types:

1. $$$id$$$ $$$nw$$$ — weight $$$w_{id}$$$ of the box $$$id$$$ becomes $$$nw$$$.
2. $$$l$$$ $$$r$$$ — you should compute the minimum total energy needed to put together boxes with indices in $$$[l, r]$$$. Since the answer can be rather big, print the remainder it gives when divided by $$$1000\,000\,007 = 10^9 + 7$$$. Note that the boxes are not moved during the query, you only should compute the answer.

Note that you should minimize the answer, not its remainder modulo $$$10^9 + 7$$$. So if you have two possible answers $$$2 \cdot 10^9 + 13$$$ and $$$2 \cdot 10^9 + 14$$$, you should choose the first one and print $$$10^9 + 6$$$, even though the remainder of the second answer is $$$0$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of boxes and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the positions of the boxes. All $$$a_i$$$ are distinct, $$$a_{i - 1} < a_i$$$ holds for all valid $$$i$$$.

The third line contains $$$n$$$ integers $$$w_1, w_2, \dots w_n$$$ ($$$1 \le w_i \le 10^9$$$) — the initial weights of the boxes.

Next $$$q$$$ lines describe queries, one query per line.

Each query is described in a single line, containing two integers $$$x$$$ and $$$y$$$. If $$$x < 0$$$, then this query is of the first type, where $$$id = -x$$$, $$$nw = y$$$ ($$$1 \le id \le n$$$, $$$1 \le nw \le 10^9$$$). If $$$x > 0$$$, then the query is of the second type, where $$$l = x$$$ and $$$r = y$$$ ($$$1 \le l_j \le r_j \le n$$$). $$$x$$$ can not be equal to $$$0$$$.

Output format:
For each query of the second type print the answer on a separate line. Since answer can be large, print the remainder it gives when divided by $$$1000\,000\,007 = 10^9 + 7$$$.

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Note:
Let's go through queries of the example:

1. $$$1\ 1$$$ — there is only one box so we don't need to move anything.
2. $$$1\ 5$$$ — we can move boxes to segment $$$[4, 8]$$$: $$$1 \cdot |1 - 4| + 1 \cdot |2 - 5| + 1 \cdot |6 - 6| + 1 \cdot |7 - 7| + 2 \cdot |10 - 8| = 10$$$.
3. $$$1\ 3$$$ — we can move boxes to segment $$$[1, 3]$$$.
4. $$$3\ 5$$$ — we can move boxes to segment $$$[7, 9]$$$.
5. $$$-3\ 5$$$ — $$$w_3$$$ is changed from $$$1$$$ to $$$5$$$.
6. $$$-1\ 10$$$ — $$$w_1$$$ is changed from $$$1$$$ to $$$10$$$. The weights are now equal to $$$w = [10, 1, 5, 1, 2]$$$.
7. $$$1\ 4$$$ — we can move boxes to segment $$$[1, 4]$$$.
8. $$$2\ 5$$$ — we can move boxes to segment $$$[5, 8]$$$.

Example input:
5 8
1 2 6 7 10
1 1 1 1 2
1 1
1 5
1 3
3 5
-3 5
-1 10
1 4
2 5

Example output:
0
10
3
4
18
7

Editorial:
Firstly, let's prove that it's always optimal to leave one of the boxes untouched. By contradiction: if all boxes will move, so some left part will move right and right part will move left. Let the total cost of shifting the whole left part by one be equal to $$$S_l$$$ and cost of the right part be $$$S_r$$$. We can replace the move of one of the parts by extra move of the other part, so we can change $$$\max(S_l, S_r)$$$ by $$$\min(S_l, S_r)$$$ — total cost doesn't increase — contradiction.
Let $$$S(l, r) = \sum\limits_{i=l}^{r}{w_i}$$$. Then, secondly, let's prove that for some segment $$$[l, r]$$$ it's always optimal to choose untouched box $$$k$$$ such that $$$S(l, k-1) \le \frac{S(l, r)}{2}$$$, but $$$S(l, k) \ge \frac{S(l, r)}{2}$$$. Again: if it is not true then either $$$S(l,k - 1) > \frac{S(l, r)}{2}$$$ or $$$S(k+1, r) > \frac{S(l, r)}{2}$$$. And we again can replace either $$$S(l, k - 1)$$$ by $$$S(k, r)$$$ or $$$S(k + 1, r)$$$ by $$$S(l, k)$$$. Total cost is decreasing — contradiction.
So, finally, all we need is to process the following queries: for given $$$[l, r]$$$ find maximum $$$k$$$ that $$$S(l, k-1) \le \frac{S(l, r)}{2}$$$, but $$$S(l, k) > \frac{S(l, r)}{2}$$$ ($$$>$$$ or $$$\ge$$$ doesn't really matter). It can be done with binary search + BIT in $$$O(\log^2 n)$$$ time or by "descending" down the Segment Tree in $$$O(\log n)$$$ time.
Next part is how to calculate the answer for the known $$$k$$$. Since the cost of moving box $$$i$$$ to the right place is equal to $$$w_i (a_k - a_i - (k - i))$$$ if $$$i < k$$$ and $$$w_i (a_i - a_k - (i - k))$$$ otherwise so, if we shift from $$$a_i$$$ to $$$a_i - i$$$ then the cost to move all left indices are equal to $$$\sum\limits_{i=l}^{k-1}{w_i (a_k - a_i)} = a_k \cdot S(l, k-1) - \sum\limits_{i=l}^{k-1}{w_i a_i}$$$. The right part transforms in the same way. Since answer is modulo $$$10^9 + 7$$$ we can calculate $$$\sum\limits_{i=l}^{k-1}{(w_i a_i \mod 10^9 + 7)}$$$ using another BIT.
Result complexity is $$$O(n \log n + q \log^2 n)$$$ or $$$O((n + q) \log n)$$$ (which isn't really faster in this task).