Codeforces Round 439 (Div. 2)

發表於 更新於 分類於 ， Disqus： 文章字數： 741 所需閱讀時間 ≈ 2 分鐘
E

E. The Untended Antiquity

time limit per test 2 seconds
memory limit per test 512 megabytes
input standard input
output standard output

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 $r_1$ $c_1$ $r_2$ $c_2$” means Oshino’s placing barriers around a rectangle with two corners being ($r_1$, $c_1$) and ($r_2$, $c_2$) and sides parallel to squares sides. Similarly, “2 $r_1$ $c_1$ $r_2$ $c_2$” 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 $r_1$ $c_1$ $r_2$ $c_2$” means that Koyomi tries to walk from ($r_1$, $c_1$) to ($r_2$, $c_2$) 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, $r_1$, $c_1$, $r_2$, $c_2$ (1 ≤ t ≤ 3, 1 ≤ $r_1$, $r_2$ ≤ n, 1 ≤ $c_1$, $c_2$ ≤ m) — the type and two coordinates of an action. Additionally, the following holds depending on the value of t:

If t = 1: 2 ≤ $r_1$ ≤ $r_2$ ≤ n - 1, 2 ≤ $c_1$ ≤ $c_2$ ≤ m - 1;
If t = 2: 2 ≤ $r_1$ ≤ $r_2$ ≤ n - 1, 2 ≤ $c_1$ ≤ $c_2$ ≤ 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

1
2
3
4
5
6
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

1
2
No
Yes

input

1
2
3
4
5
6
7
8
9
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

1
2
3
No
Yes
No

Solution

二维线段树+set/vector/rand

二维数状数组+rand+’+’

二维数状数组+rand+’^’

官方解答

我读官方解答读下来，发现官方解答用的是一维线段树 只在左右方向进行划分，对于横坐标划分后保存 纵向的 启始和结束以及_id 这样看得话_id是否有点多余？？？ 但好像写出来比比较 _u和_d 看上去简洁 不过这个都不影响复杂度，然后我尝试了把 _u和_d进行编码 当作返回，结论是 不可以的，因为 可能目标两个的点所在的矩形 不是同一个，但 这两个矩形的上下的分化是一样的:-)僵硬，结论还是要_id的

我反正还没想到2D的线段树也就是 四叉树 加信息标注 要怎么做？？？？ need help 上面三个选手的代码都是带rand()

然后官方题解用了 好多C++新的东西 比如 auto and 低头

以及看别人的代码发现 手工编码解码很少了，大家都用的makepair 甚至两重makepair