http://www.elijahqi.win/archives/1159
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 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.
二维树状数组。。
大概询问是问我们 每次给出围栏的范围或者删除这个围栏
问文中的我能否不跨围栏到达给定的另一端
有几点是值得推敲的 首先这个围栏不是在格子上，是在格子边缘
其次数据给的所有围栏是不会相交的
不会相交那么很好 回想一下以前写过的二维树状数组
相当于是给区间的四个点加值
上面的二维线段树
好了 回到题目 每次给一个围栏，如果是围栏里，任意的点你都可以到达
那么不妨给这个区域集体染色然后判断一下询问的点是否颜色相同就好
颜色不同说明中间一定有障碍物无法逾越
用map查找（方便）懒
#include<cstdio>#include<map>#include<cstdlib>#include<ctime>#define N 2650using namespace std;inline char gc(){static char now[1<<16], *S, *T;if(S==T){T=(S=now)+fread(now, 1, 1<<16, stdin); if(S==T)return EOF;}return *S++;}map<pair<pair<int, int>, pair<int, int> >, int>mm;inline int read(){int x=0;char ch=gc();while (ch<'0'||ch>'9') ch=gc();while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();}return x;}inline int random (){int mod=1e9;long long x=10000,a=rand()%10000,b=rand()%10000,c=rand()%10000;return (a*x*x+b*x+c)%mod;}long long s[N][N];int n,m,q;inline void insert1(int x,int y,int z){for (int i=x;i<=n;i+=i&(-i))for (int j=y;j<=m;j+=j&(-j)){s[i][j]+=z;}}inline long long query(int x,int y){long long tmp=0;for (int i=x;i>0;i-=i&(-i))for (int j=y;j>0;j-=j&(-j)){tmp+=s[i][j];}return tmp;}int main(){freopen("cf.in","r",stdin);n=read();m=read();q=read();srand(time(0));for (int i=1;i<=q;++i){int op=read(),x1=read(),y1=read(),x2=read(),y2=read();if (op==1){int stamp=random();mm[make_pair(make_pair(x1,y1),make_pair(x2,y2))]=stamp;insert1(x1,y1,stamp);insert1(x1,y2+1,-stamp);insert1(x2+1,y1,-stamp);insert1(x2+1,y2+1,stamp);}if (op==2){int stamp=mm[make_pair(make_pair(x1,y1),make_pair(x2,y2))];insert1(x1,y1,-stamp);insert1(x1,y2+1,stamp);insert1(x2+1,y1,stamp);insert1(x2+1,y2+1,-stamp);}if (op==3){long long stamp1=query(x1,y1),stamp2=query(x2,y2);if (stamp1==stamp2) printf("Yes\n");else printf("No\n");}}return 0;}
