
ZOJ Problem Set  4050
DreamGrid is creating a piece of pixel art on a grid of $n$ rows and $m$ columns where all the cells are initially white. As a beginner pixel artist, he can only paint horizontal or vertical lines on the grid. Let's denote the cell on the $i$th row and the $j$th column as $(i, j)$. Formally speaking,
After some time, DreamGrid has left $k$ nonintersecting lines on the grid. As DreamGrid is also an enthusiast for competitive programming, he is interested in the mathematical properties of his artwork as well. Let $G_i$ be the subgrid containing the the first $i$ rows of the original $n \times m$ grid. We denote $s_i$ as the number of black cells in $G_i$ and $c_i$ as the number of black connected components in $G_i$. Can you help DreamGrid calculate the value of $s_i$ and $c_i$ for all $1 \le i \le n$, so that he can have a deeper insight into his artwork? Note that in this problem, two black cells $(r_a, c_a)$ and $(r_b, c_b)$ are in the same connected component, if there exists a sequence of black cells $(r_1, c_1), (r_2, c_2), \dots, (r_k, c_k)$ such that $r_1 = r_a, c_1 = c_a, r_k = r_b, c_k = c_b$ and for all $1 \le i < k$, $(r_i, c_i)$ and $(r_{i+1}, c_{i+1})$ share an edge. InputThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains three integers $n$, $m$ and $k$ ($1 \le n, m, k \le 10^5$), indicating the number of rows and the number of columns of the grid, and the number of lines DreamGrid has painted. The following $k$ lines each contains four integers $r_1, c_1, r_2, c_2$ ($1 \le r_1 \le r_2 \le n$, $1 \le c_1 \le c_2 \le m$, $r_1 = r_2$ or $c_1 = c_2$) indicating the lines DreamGrid painted on the grid.
It's guaranteed that
OutputFor each test case output $n$ lines where the $i$th line contains two integers $s_i$ and $c_i$ separated by a space, indicating the number of black cells and the number of black connected components in the first $i$ rows of the grid. Sample Input3 2 5 2 1 1 1 2 2 3 2 5 2 5 2 1 1 1 3 2 3 2 5 3 3 3 1 1 1 2 3 1 3 2 1 3 2 3 Sample Output2 1 5 2 3 1 6 1 3 1 4 1 6 2 HintThe following image illustrates the sample test cases. The number in the cell indicates the index of the corresponding line. For the third sample test case, it's obvious that there are 3 black cells and 1 black connected components in the first row, 4 black cells and 1 black connected components in the first two rows, and 6 black cells and 2 black connected components in all the three rows. So the answer is "3 1", "4 1" and "6 2". Author: ZHAO, Yueqi Source: The 2018 ACMICPC Asia Qingdao Regional Contest, Online 