Staircases
Contest: Educational Codeforces Round 115 (Rated for Div. 2)
Difficulty rating: 2100
Tags: brute force, combinatorics, data structures, dfs and similar, dp, implementation, math

You are given a matrix, consisting of $$$n$$$ rows and $$$m$$$ columns. The rows are numbered top to bottom, the columns are numbered left to right.

Each cell of the matrix can be either free or locked.

Let's call a path in the matrix a staircase if it:

- starts and ends in the free cell;
- visits only free cells;
- has one of the two following structures:   the second cell is $$$1$$$ to the right from the first one, the third cell is $$$1$$$ to the bottom from the second one, the fourth cell is $$$1$$$ to the right from the third one, and so on;  the second cell is $$$1$$$ to the bottom from the first one, the third cell is $$$1$$$ to the right from the second one, the fourth cell is $$$1$$$ to the bottom from the third one, and so on.

In particular, a path, consisting of a single cell, is considered to be a staircase.

Here are some examples of staircases:

Initially all the cells of the matrix are free.

You have to process $$$q$$$ queries, each of them flips the state of a single cell. So, if a cell is currently free, it makes it locked, and if a cell is currently locked, it makes it free.

Print the number of different staircases after each query. Two staircases are considered different if there exists such a cell that appears in one path and doesn't appear in the other path.

Input format:
The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n, m \le 1000$$$; $$$1 \le q \le 10^4$$$) — the sizes of the matrix and the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x \le n$$$; $$$1 \le y \le m$$$) — the description of each query.

Output format:
Print $$$q$$$ integers — the $$$i$$$-th value should be equal to the number of different staircases after $$$i$$$ queries. Two staircases are considered different if there exists such a cell that appears in one path and doesn't appear in the other path.

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

Example input:
2 2 8
1 1
1 1
1 1
2 2
1 1
1 2
2 1
1 1

Example output:
5
10
5
2
5
3
1
0

Example input:
3 4 10
1 4
1 2
2 3
1 2
2 3
3 2
1 3
3 4
1 3
3 1

Example output:
49
35
24
29
49
39
31
23
29
27

Editorial:
The solution consist of two main parts: calculate the initial number of staircases and recalculate the number of staircases on query.
The constraints were pretty loose, so we'll do the first part in $$$O(nm)$$$ and the second part in $$$O(n + m)$$$ per query.
However, it's worth mentioning that faster is possible. The first part can surely be done in $$$O(n + m)$$$ and can probably be done in $$$O(1)$$$. The second part can be done in $$$O(\log n)$$$ per query.
It's important to notice is that the only staircase that satisfy the requirements for both types is the staircase that consists of a single cell. Thus, staircases of both types can be calculated almost separately.
Let's define "base" staircases as the staircases that can't be prolonged further in any direction. There are $$$O(n + m)$$$ of them on the grid.
If a staircase consists of at least two cells, it's a part of exactly one base staircase. At the same time, every segment of a base staircase is a valid staircase by itself.
Thus, the main idea of calculating the initial answer is the following. Isolate each base staircase and determine its length $$$\mathit{len}$$$ (possibly, in $$$O(n + m)$$$). Add $$$\binom{len-1}{2}$$$ (the number of segments of length at least $$$2$$$) to the answer. Add extra $$$nm$$$ one cell staircases afterwards.
If you draw the base staircases on the grid, you can easily determine their starting cell. The base staircases, that start by going one cell to the right, start from the first row. The base staircases, that start by going one cell to the bottom, start from the first column. Notice that both types can start from cell $$$(1, 1)$$$.
The updates can be handled the following way. The answer always changes by the number of staircases that pass through cell $$$(x, y)$$$ (if you ignore its state). If the cell becomes free, then these staircases are added to the answer. Otherwise, they are subtracted from it.
That can be calculated for two cases as well. Go first down, then right, as far as possible. Let it be $$$cnt_1$$$ steps. Go first left, then up, as far as possible. Let it be $$$cnt_2$$$ steps. Then $$$cnt_1 \cdot cnt_2$$$ staircases are added to the answer. Then change the order of steps in both directions to calculate the other type of staircases. Beware of one cell staircases again.
To achieve $$$O(n + m)$$$ for precalc, you can calculate the length of each base staircase with a formula. To achieve $$$O(\log n)$$$ per query, you can first enumerate cells in each base staircase separately, then maintain the set of segments of adjacent free cells in it.