P15760 [JAG 2025 Summer Camp #1] Path Flipping

For a grid with each cell colored either white or black, let us define the **beauty** of the grid as follows: - Consider performing the following operation any number of times: - Choose a path from the upper-left corner to the lower-right corner, consisting only of downward and rightward moves. Invert the colors of all cells on the chosen path. - The **beauty** of the grid is defined as the maximum possible number of cells colored black. You have a grid with $H$ rows and $W$ columns. Initially, all cells are colored white. You need to process $Q$ queries in order. The $i$-th query is given in the following format: - You are given two integers $t_i$ and $x_i$. - If $t_i = 1$, invert the colors of all cells in the $x_i$-th row from the top. - If $t_i = 2$, invert the colors of all cells in the $x_i$-th column from the left. - Then, find the **beauty** of the current grid.

The input is given in the following format: $$\begin{aligned} & H \ W \ Q \\ & t_1 \ x_1 \\ & \vdots \\ & t_Q \ x_Q \end{aligned}$$ - $1 \leq H, W \leq 200\ 000$ - $1 \leq Q \leq 200\ 000$ - $t_i \in \{1, 2\}$ ($1 \leq i \leq Q$) - $t_i = 1 \implies 1 \leq x_i \leq H$ ($1 \leq i \leq Q$) - $t_i = 2 \implies 1 \leq x_i \leq W$ ($1 \leq i \leq Q$) - All input values are integers.

Output $Q$ lines. On the $i$-th line ($1 \leq i \leq Q$), output the answer for the $i$-th query.