当覆盖两点的最小矩形不同时，一定不可达
这样的问题不难想到经典的二维树状数组+差分来支持二维区间覆盖+查询
对于覆盖操作 我们可以差分的给这个矩阵里加上一个编号
对于操墙操作 我们可以反着减去这个编号
对于查询 就查询这两个点的值是否相同 编号的累积不影响 因为只有在同一个墙内才会累积
注意 如果只是单单的把编号从1开始标号是不够的 因为会出现1+3=2+2这类情况
需要哈希
#include<bits/stdc++.h> #define uint unsigned int #define N 2505 #define lowbit(x) x&(-x) #define base 19260817 using namespace std; template<class T> inline void read(T &x) { x=0; int f=1; static char ch=getchar(); while((!isdigit(ch))&&ch!='-') ch=getchar(); if(ch=='-') f=-1; while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); x*=f; } int tree[N][N],n,m,id; inline void add(int x,int y,int z) { for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=m;j+=lowbit(j)) tree[i][j]+=z; } inline int query(int x,int y) { int ans=0; for(int i=x;i;i-=lowbit(i)) for(int j=y;j;j-=lowbit(j)) ans+=tree[i][j]; return ans; } /*struct matrix { int x1,y1,x2,y2; inline bool operator<(const matrix &a) const { if(x1 < a.x1) return 1; if(y1 < a.y1) return 1; if(x2 < a.x2) return 1; if(y2 < a.y2) return 1; return 0; } }; map <matrix,int> M;*/ int main() { int Q; read(n),read(m),read(Q); for(int i=1,x1,y1,x2,y2,opt;i<=Q;i++) { read(opt),read(x1),read(y1),read(x2),read(y2); uint num=x1*base*base*base+x2*base*base+y1*base+y2; //当覆盖两点的最小矩形不同时，一定不可达 if(opt==1) { // M[(matrix){x1,y1,x2,y2}]=++id; add(x1,y1,num); add(x1,y2+1,-num); add(x2+1,y1,-num); add(x2+1,y2+1,num); } if(opt==2) { // int num=M[(matrix){x1,y1,x2,y2}]; add(x1,y1,-num); add(x1,y2+1,num); add(x2+1,y1,num); add(x2+1,y2+1,-num); } if(opt==3) { if(query(x1,y1)==query(x2,y2)) puts("Yes"); else puts("No"); } } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9884524.html
