题意
一个地图,然后三种操作
1.一个矩阵四周加上障碍
2.一个矩阵四周的障碍消除
3.问你两个点之间是否纯在一条路径不经过障碍
题解
我们可以给每一个矩阵一个hash值
然后将矩阵里面的点都加上这个数
如果是撤销障碍就减去
然后判断两个点是否连通就看一下他的数是多少
至于怎么维护这个矩阵加上,我们可以用一个类似差分的思想,然后用树状数组维护一下
就像下图:
然后对于一个点得到他的矩阵和就好了
#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<map>using namespace std;int n,m,q;long long tr[2505][2505];long long mod=1e9+7;int lb(int x){return x&(-x);}void add(int a,int b,long long v){for(int i=a;i<=n;i+=lb(i)){for(int j=b;j<=m;j+=lb(j)){tr[i][j]+=v;}}}long long get(int a,int b){long long ans=0;for(int i=a;i>=1;i-=lb(i)){for(int j=b;j>=1;j-=lb(j)){ans+=tr[i][j];}}return ans;}int main(){while(~scanf("%d%d%d",&n,&m,&q)){memset(tr,0,sizeof(tr));map<pair<pair<int ,int>, pair<int ,int> >,long long > mp;long long id=1;while(q--){int t,a1,b1,a2,b2;scanf("%d%d%d%d%d",&t,&a1,&b1,&a2,&b2);if(t==1){id*=mod;mp[make_pair(make_pair(a1,b1),make_pair(a2,b2))]=id;add(a1,b1,id);add(a2+1,b2+1,id);add(a1,b2+1,-id);add(a2+1,b1,-id);}else if(t==2){long long tid=mp[make_pair(make_pair(a1,b1),make_pair(a2,b2))];add(a1,b1,-tid);add(a2+1,b2+1,-tid);add(a1,b2+1,tid);add(a2+1,b1,tid);}else{long long tp1=get(a1,b1);long long tp2=get(a2,b2);if(tp1==tp2)printf("Yes\n");elseprintf("No\n");}}}}