Desktop Rearrangement
Contest: Codeforces Round 786 (Div. 3)
Difficulty rating: 1800
Tags: data structures, greedy, implementation

Your friend Ivan asked you to help him rearrange his desktop. The desktop can be represented as a rectangle matrix of size $$$n \times m$$$ consisting of characters '.' (empty cell of the desktop) and '*' (an icon).

The desktop is called good if all its icons are occupying some prefix of full columns and, possibly, the prefix of the next column (and there are no icons outside this figure). In other words, some amount of first columns will be filled with icons and, possibly, some amount of first cells of the next (after the last full column) column will be also filled with icons (and all the icons on the desktop belong to this figure). This is pretty much the same as the real life icons arrangement.

In one move, you can take one icon and move it to any empty cell in the desktop.

Ivan loves to add some icons to his desktop and remove them from it, so he is asking you to answer $$$q$$$ queries: what is the minimum number of moves required to make the desktop good after adding/removing one icon?

Note that queries are permanent and change the state of the desktop.

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 2 \cdot 10^5$$$) — the number of rows in the desktop, the number of columns in the desktop and the number of queries, respectively.

The next $$$n$$$ lines contain the description of the desktop. The $$$i$$$-th of them contains $$$m$$$ characters '.' and '*' — the description of the $$$i$$$-th row of the desktop.

The next $$$q$$$ lines describe queries. The $$$i$$$-th of them contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le n; 1 \le y_i \le m$$$) — the position of the cell which changes its state (if this cell contained the icon before, then this icon is removed, otherwise an icon appears in this cell).

Output format:
Print $$$q$$$ integers. The $$$i$$$-th of them should be the minimum number of moves required to make the desktop good after applying the first $$$i$$$ queries.

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

Example input:
4 4 8
..**
.*..
*...
...*
1 3
2 3
3 1
2 3
3 4
4 3
2 3
2 2

Example output:
3
4
4
3
4
5
5
5

Example input:
2 5 5
*...*
*****
1 3
2 2
1 3
1 5
2 3

Example output:
2
3
3
3
2

Editorial:
I've seen a lot of data structures solutions for this problem, but author's solution doesn't use them and works in $$$O(nm + q)$$$.
Firstly, let's change our matrix to a string $$$s$$$, because it will be easier to work with a string than with a matrix. The order of characters will be from top to bottom, from left to right (i. e. the outer cycle by columns, and the inner by rows). Then, let's calculate $$$sum$$$ — the number of icons on the desktop (the number of '*' in $$$s$$$). Then the answer will be, obviously, the number of dots on the prefix of $$$s$$$ of size $$$sum$$$.
Now let's deal with queries. It can be shown that one query changes our answer by no more than $$$1$$$.
Let $$$p = ny + x$$$ be the position of the cell that is being changed in $$$s$$$ (zero-indexed). Then, if $$$p < sum$$$, there are two cases. If $$$s_p$$$ is '.', then we have one more icon on our prefix, so the answer decreases by one (because we filled one empty space in the good desktop). Otherwise, it increases by one (because this icon is outside our prefix).
Then let's change the corresponding character by the opposite. After that, we should move our right border ($$$sum$$$) accordingly to the new number of icons. Note that this border is exclusive. If $$$s_p$$$ becomes '*', then we will increase the variable $$$sum$$$. But before that, if $$$s_{sum}$$$ is '.', then there should be an icon, and it is not here yet, so the answer increases. Otherwise, our border will decrease. Then, if $$$s_{sum - 1}$$$ is '.', then the answer decreases (because there was a place for an icon, and now it is not needed anymore).
Time complexity: $$$O(nm + q)$$$.