E. The Untended Antiquity
time limit per test2 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
Adieu l’ami.
Koyomi is helping Oshino, an acquaintance of his, to take care of an open space around the abandoned Eikou Cram School building, Oshino’s makeshift residence.
The space is represented by a rectangular grid of n × m cells, arranged into n rows and m columns. The c-th cell in the r-th row is denoted by (r, c).
Oshino places and removes barriers around rectangular areas of cells. Specifically, an action denoted by “1 r1 c1 r2 c2” means Oshino’s placing barriers around a rectangle with two corners being (r1, c1) and (r2, c2) and sides parallel to squares sides. Similarly, “2 r1 c1 r2 c2” means Oshino’s removing barriers around the rectangle. Oshino ensures that no barriers staying on the ground share any common points, nor do they intersect with boundaries of the n × m area.
Sometimes Koyomi tries to walk from one cell to another carefully without striding over barriers, in order to avoid damaging various items on the ground. “3 r1 c1 r2 c2” means that Koyomi tries to walk from (r1, c1) to (r2, c2) without crossing barriers.
And you’re here to tell Koyomi the feasibility of each of his attempts.
Input
The first line of input contains three space-separated integers n, m and q (1 ≤ n, m ≤ 2 500, 1 ≤ q ≤ 100 000) — the number of rows and columns in the grid, and the total number of Oshino and Koyomi’s actions, respectively.
The following q lines each describes an action, containing five space-separated integers t, r1, c1, r2, c2 (1 ≤ t ≤ 3, 1 ≤ r1, r2 ≤ n, 1 ≤ c1, c2 ≤ m) — the type and two coordinates of an action. Additionally, the following holds depending on the value of t:
If t = 1: 2 ≤ r1 ≤ r2 ≤ n - 1, 2 ≤ c1 ≤ c2 ≤ m - 1;
If t = 2: 2 ≤ r1 ≤ r2 ≤ n - 1, 2 ≤ c1 ≤ c2 ≤ m - 1, the specified group of barriers exist on the ground before the removal.
If t = 3: no extra restrictions.
Output
For each of Koyomi’s attempts (actions with t = 3), output one line — containing “Yes” (without quotes) if it’s feasible, and “No” (without quotes) otherwise.
Examples
input
5 6 5
1 2 2 4 5
1 3 3 3 3
3 4 4 1 1
2 2 2 4 5
3 1 1 4 4
output
No
Yes
input
2500 2500 8
1 549 1279 1263 2189
1 303 795 1888 2432
1 2227 622 2418 1161
3 771 2492 1335 1433
1 2017 2100 2408 2160
3 48 60 798 729
1 347 708 1868 792
3 1940 2080 377 1546
output
No
Yes
No
Note
For the first example, the situations of Koyomi’s actions are illustrated below.
题目链接：CF 869E
还是好菜啊~哎，这题如果想到了用$Hash$就是很简单的二维树状数组区间更新单点求和的模板题……不过感觉题目没讲清楚，删除的矩阵一定是之前出现过的，由于题目限制矩阵之间不会存在任何交集，那么判断两个点能否连通只要看这两个点是否被框到了同一个矩阵中即可，那么给每一个矩阵映射一个唯一的值，然后用二维树状数组更新这个矩阵内的点，判断两个点被哪些矩阵套过就在$BIT$上求和看是否相等就可以了，写多维$BIT$的时候要注意除了第一维,后面的$y$不能直接拿来用，因为对于每一个$x$都要从$y$开始更新，因此要用一个变量代替$y$去更新，这里卡了好久……
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 2510;
typedef unsigned long long ULL;
ULL seed = 1e9 + 7;
ULL T[N][N];
map<pair<int, pair<int, pair<int, int> > >, ULL>pos;
int n, m;
void init()
{
CLR(T, 0);
pos.clear();
}
void add(int x, int y, ULL v)
{
while (x <= n)
{
int yy = y;
while (yy <= m)
{
T[x][yy] += v;
yy += (yy & -yy);
}
x += (x & -x);
}
}
ULL sum(int x, int y)
{
ULL ret = 0;
while (x)
{
int yy = y;
while (yy)
{
ret += T[x][yy];
yy -= (yy & -yy);
}
x -= (x & -x);
}
return ret;
}
int main(void)
{
int q, x1, y1, x2, y2, i, ops;
while (~scanf("%d%d%d", &n, &m, &q))
{
init();
ULL Hash = 1ULL;
for (i = 0; i < q; ++i)
{
scanf("%d%d%d%d%d", &ops, &x1, &y1, &x2, &y2);
if (ops == 1)
{
Hash *= seed;
add(x1, y1, Hash);
add(x1, y2 + 1, -Hash);
add(x2 + 1, y1, -Hash);
add(x2 + 1, y2 + 1, Hash);
pos[ {x1, {y1, {x2, y2}}}] = Hash;
}
else if (ops == 2)
{
ULL del = pos[ {x1, {y1, {x2, y2}}}];
add(x1, y1, -del);
add(x1, y2 + 1, del);
add(x2 + 1, y1, del);
add(x2 + 1, y2 + 1, -del);
}
else
puts(sum(x1, y1) == sum(x2, y2) ? "Yes" : "No");
}
}
return 0;
}