34465번 - Snakes on a Grid 서브태스크다국어

On a rectangular grid, a snake of size $k$ is defined to be a subset of cells that is formed by taking the first $k$ numbered cells in the following figure, where cells are numbered along a path with alternating right and down steps:

Additionally, subsets that are rotations, translations, or reflections of these shapes are also considered snakes. A grid is considered good if every connected component consisting of equal values in the grid is a snake.

Busy Beaver has an $N \times M$ grid with rows numbered $0, \dots, N-1$ and columns numbered $0, \dots, M-1$, where each cell $(i, j)$ in row $i$, column $j$ has a value $a_{ij}$. Since he's afraid of snakes, he wants you to answer $Q$ of the following queries: given a contiguous subrectangle of the grid, determine whether or not the subgrid is good.

The first line contains 2 integers, $N$ and $M$ ($1 \leq N, M \leq 1000$) --- the dimensions of the grid.

Each of the next $N$ rows contains $M$ integers, with the $j$-th element of the $i$-th row being $a_{i,j}$ ($1 \leq a_{i, j} \leq 10^6$) --- the number written in the $j$-th cell of the $i$-th row.

The next line contains a single integer, $Q$ ($1 \leq Q \leq 5 \cdot 10^5$) --- the number of queries.

The next $Q$ lines describe the queries, Each line contains 4 integers $x_1$, $y_1$, $x_2$, $y_2$ $(0 \leq x_1 \leq x_2 < N,$ $ 0 \leq y_1 \leq y_2 < M)$, representing a query asking whether the rectangular subgrid with top left corner at $(x_1, y_1)$ and bottom right corner at $(x_2, y_2)$ is good.

For each query, output "YES" (without quotes) if the corresponding subgrid consists only of snakes, and "NO" (without quotes) otherwise.

If we color the sample grid with respect to the value in each cell, we get

In the first query, all components are snakes.

In the second query, the component that is not a snake is colored in black.

In the third query, the component that is not a snake is colored in black.

In the fourth query, all components are snakes.

In the fifth query, the component that is not a snake is colored in black.