Dune II: Battle For Arrakis
Contest: Kotlin Heroes: Episode 4
Difficulty rating: 2000
Tags: *special, data structures, greedy, math

You're at the last mission in one very old and very popular strategy game Dune II: Battle For Arrakis. The map of the mission can be represented as a rectangular matrix of size $$$n \times m$$$. Initially, there are $$$a_{i, j}$$$ units of your army in the cell $$$(i, j)$$$.

You want to prepare for the final battle, so you want to move all your army into exactly one cell of the map (i.e. $$$nm-1$$$ cells should contain $$$0$$$ units of the army and the remaining cell should contain the entire army).

To do this, you can do some (possibly, zero) number of moves. During one move, you can select exactly one unit from some cell and move it to one of the adjacent by side cells. I.e. from the cell $$$(i, j)$$$ you can move the unit to cells:

- $$$(i - 1, j)$$$;
- $$$(i, j - 1)$$$;
- $$$(i + 1, j)$$$;
- $$$(i, j + 1)$$$.

Of course, you want to move all your army into exactly one cell as fast as possible. So, you want to know the minimum number of moves you need to do that.

And, of course, life goes on, so the situation on the map changes. There are $$$q$$$ updates, the $$$i$$$-th update is denoted by three integers $$$x, y, z$$$. This update affects the army in the cell $$$(x, y)$$$: after this update, the number of units in the cell $$$(x, y)$$$ becomes $$$z$$$ (i.e. you replace $$$a_{x, y}$$$ with $$$z$$$).

Also, you want to determine, for each $$$i$$$, the minimum number of moves needed to move your entire army into exactly one cell with the first $$$i$$$ updates applied to the initial map. In other words, the map after the $$$i$$$-th update equals the initial map with the first $$$i$$$ updates applied to it.

Input format:
The first line of the input contains three integers $$$n, m$$$ and $$$q$$$ ($$$1 \le n, m \le 1000; 1 \le q \le 5000$$$) — the size of the matrix and the number of updates correspondingly.

The next $$$n$$$ lines contain $$$m$$$ integers each, where the $$$j$$$-th integer in the $$$i$$$-th line is $$$a_{i, j}$$$ ($$$1 \le a_{i, j} \le 10^9$$$) — the number of units in the cell $$$(i, j)$$$.

The next $$$q$$$ lines contain three integers each, where the $$$i$$$-th line contains three integers $$$x_i, y_i$$$ and $$$z_i$$$ ($$$1 \le x_i \le n; 1 \le y_i \le m; 1 \le z_i \le 10^9$$$) — the cell in which the number of units updates and the new number of units in this cell correspondingly.

Output format:
Print $$$q+1$$$ integers $$$r_0, r_1, r_2, \dots, r_n$$$, where $$$r_0$$$ is the minimum number of moves you need to move all your army into exactly one cell, and $$$r_i$$$ for all $$$i$$$ from $$$1$$$ to $$$q$$$ is the minimum number of moves you need to move all your army into exactly one cell after the first $$$i$$$ updates.

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

Example input:
3 3 1
1 2 3
2 1 2
1 1 2
2 3 100

Example output:
21 22

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

Example output:
123 135 129 145

Editorial:
Consider the map in $$$0$$$-indexation. If we move the entire army into the cell $$$(x, y)$$$ then the answer can be represented as $$$\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{m-1} (|x-i| + |y-j|) \cdot a_{i, j}$$$. This can be rewritten as $$$\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{m-1} |x-i| \cdot a_{i, j} + \sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{m-1} |y-j| \cdot a_{i, j}$$$. Let $$$xs_i$$$ be the number of units in the $$$i$$$-th row ($$$xs_i = \sum\limits_{j=0}^{m-1} a_{i, j}$$$) and $$$ys_j$$$ be the number of units in the $$$j$$$-th column. Then the last equation can be represented as $$$\sum\limits_{i=0}^{n-1} |x-i| \cdot xs_i + \sum\limits_{j=0}^{m-1} |y-j| \cdot ys_j$$$.
So, we see that the problem can be solved independently for rows and columns. Now we have at least $$$O(nmq)$$$ solution. How do we speed it up?
Consider the following sequence: $$$\underbrace{0, 0, \dots, 0}_{xs_0}, \underbrace{1, 1, \dots, 1}_{xs_1}, \dots, \underbrace{n-1, n-1, \dots, n-1}_{xs_{n-1}}$$$. Let $$$sum$$$ be the sum of all $$$a_{i, j}$$$. Then we can show that it is always optimally to move the entire army into the cell which has the index $$$\lfloor\frac{sum-1}{2}\rfloor$$$ in the sequence above (in other words, it is always optimally to move the entire army to the median). So, if we know the real value of this cell in the sequence above, we can calculate the answer for rows in $$$O(n)$$$. And we can find the value of this cell in $$$O(n)$$$ (just find the first such $$$x$$$ that $$$\sum\limits_{i=0}^{x} \ge \lfloor\frac{sum-1}{2}\rfloor$$$.
We can do the same for columns and the array $$$ys$$$. And now we have the required point $$$(x, y)$$$ and can calculate the answer in $$$O(n+m)$$$. So this part costs $$$O(n+m)$$$ in total.
And we can process the queries easily: because we only use $$$a$$$, $$$sum$$$, $$$xs$$$ and $$$ys$$$ as precalculated values, we can change them according to the query and solve the problem in $$$O(n+m)$$$ again.
Total time complexity: $$$O((n+m)q)$$$.