(Writer: kyopro_friends, Editorial: sataashun)

First, the board looks like as shown below (for convenience we use \(H\) and \(W\) as the vertical and horizontal size, but at first \(H=W=N\)). The blue border denotes the black stones and the red shaded area denotes the white stones.

It seems complicated because the queries of different directions affect with each other. But let’s assume that we have received a query \((1, x)\) to the current board (It is similar for \((2, x)\)). Assuming \(2 \leq x \leq W\), the board becomes like as follows:

Here, for every \(j\)-th column (\(x + 1 \leq j < W)\), we can see that the column is no longer affected by horizontal queries (of \((2, x)\)). So we can process the remaining query by assuming the range of purple rectangle as the first image.

We assumed \(2 \leq x \leq W\) for the query, but for the remaining range of \(x\), we can find the number of stones being flipped in an \(O(1)\) time by storing \(b_x := \) the coordinate of leftmost white stone in \(x\)-th column, by the assumption of the operation of shrinking the frame.

Similarly we can store the similar information \((a)\) for the rows and process the queries while shrinking the frame if the segments is in the current frame and updating \(a\) or \(b\).

Since each element of \(a\) and \(b\) is updated only when it drops out of the frame, so the total time complexity for all the queries is \(\mathrm{O}(N + Q)\).

Sample Code (C++)