1679C.md (3427B)
1 Source: https://codeforces.com/problemset/problem/1679/C 2 3 C. Rooks Defenders 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You have a square chessboard of size $n \times n$. Rows are numbered from top to bottom with numbers from $1$ to $n$, and columns — from left to right with numbers from $1$ to $n$. So, each cell is denoted with pair of integers $(x, y)$ ($1 \le x, y \le n$), where $x$ is a row number and $y$ is a column number. 22 23 You have to perform $q$ queries of three types: 24 25 * Put a new rook in cell $(x, y)$. 26 * Remove a rook from cell $(x, y)$. It's guaranteed that the rook was put in this cell before. 27 * Check if each cell of subrectangle $(x_1, y_1) - (x_2, y_2)$ of the board is attacked by at least one rook. 28 29 Subrectangle is a set of cells $(x, y)$ such that for each cell two conditions are satisfied: $x_1 \le x \le x_2$ and $y_1 \le y \le y_2$. 30 31 Recall that cell $(a, b)$ is attacked by a rook placed in cell $(c, d)$ if either $a = c$ or $b = d$. In particular, the cell containing a rook is attacked by this rook. 32 33 Input 34 35 The first line contains two integers $n$ and $q$ ($1 \le n \le 10^5$, $1 \le q \le 2 \cdot 10^5$) — the size of the chessboard and the number of queries, respectively. 36 37 Each of the following $q$ lines contains description of a query. Description begins with integer $t$ ($t \in \{1, 2, 3\}$) which denotes type of a query: 38 39 * If $t = 1$, two integers $x$ and $y$ follows ($1 \le x, y \le n$) — coordinated of the cell where the new rook should be put in. It's guaranteed that there is no rook in the cell $(x, y)$ at the moment of the given query. 40 * If $t = 2$, two integers $x$ and $y$ follows ($1 \le x, y \le n$) — coordinates of the cell to remove a rook from. It's guaranteed that there is a rook in the cell $(x, y)$ at the moment of the given query. 41 * If $t = 3$, four integers $x_1, y_1, x_2$ and $y_2$ follows ($1 \le x_1 \le x_2 \le n$, $1 \le y_1 \le y_2 \le n$) — subrectangle to check if each cell of it is attacked by at least one rook. 42 43 It's guaranteed that among $q$ queries there is at least one query of the third type. 44 45 Output 46 47 Print the answer for each query of the third type in a separate line. Print "Yes" (without quotes) if each cell of the subrectangle is attacked by at least one rook. 48 49 Otherwise print "No" (without quotes). 50 51 Example 52 53 Input 54 55 ``` 56 8 10 57 1 2 4 58 3 6 2 7 2 59 1 3 2 60 3 6 2 7 2 61 1 4 3 62 3 2 6 4 8 63 2 4 3 64 3 2 6 4 8 65 1 4 8 66 3 2 6 4 8 67 ``` 68 69 Output 70 71 ``` 72 No 73 Yes 74 Yes 75 No 76 Yes 77 ``` 78 79 Note 80 81 Consider example. After the first two queries the board will look like the following picture (the letter $R$ denotes cells in which rooks are located, the subrectangle of the query of the third type is highlighted in green): 82 83  84 85 Chessboard after performing the third and the fourth queries: 86 87  88 89 Chessboard after performing the fifth and the sixth queries: 90 91  92 93 Chessboard after performing the seventh and the eighth queries: 94 95  96 97 Chessboard after performing the last two queries: 98 99 