CodeForces 869E The Untended Antiquity 二维树状数组，随机hash

CodeForces 869E

题意： n*m 的格子，有三种操作， 1、在一个矩形周围加一层障碍。2、把一个矩形周围的障碍去掉。 3、询问两个格子是否可达。     题目保证不会有矩形障碍交叉，且去掉的矩形一定是在前面已给出的。

tags：

知道二维树状数组的话应该很容易想到怎么做，增减矩形只要给矩形里面的格子打上这个矩形的标记，询问的时候就看两个格子的标记是否一样即可。

但这题难在给矩形一个hash值，必须要保证两个被不同矩形围着的格子上标记的hash值不一样，这其实不太可能一定保证，只能让概率尽可能小。

我们可以随机给出矩形的 hash值，具体证明看官方题解。

#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second #define PII pair<int , int > typedef long long ll; const int N = 2505;ll rd() {return rand()<<15 | rand(); }int n, m, q; ll bit[N][N]; map< pair< PII, PII > , int > mp; void add(int r, int c, int x) {for(int i=r; i<N; i+=i&-i)for(int j=c; j<N; j+=j&-j)bit[i][j] += x; } void update(int r1, int c1, int r2, int c2, int x) {add(r2+1, c2+1, -x); add(r1, c1, -x);add(r1, c2+1, x); add(r2+1, c1, x); } ll Sum(int r, int c) {ll ans = 0;for(int i=r; i; i-=i&-i)for(int j=c; j; j-=j&-j)ans += bit[i][j];return ans; }int main() {srand(time(0));rep(i,1,50) srand(rd());scanf("%d%d%d", &n, &m, &q);int t, r1, c1, r2, c2;rep(i,1,q){scanf("%d%d%d%d%d", &t, &r1, &c1, &r2, &c2);if(t==1){int rdm = rd();update(r1, c1, r2, c2, rdm);mp[MP(MP(r1,c1), MP(r2,c2))] = rdm;}else if(t==2){int tmp = mp[MP(MP(r1,c1), MP(r2,c2))];update(r1, c1, r2, c2, -tmp);}else{ll ans1=Sum(r1, c1), ans2=Sum(r2, c2);if(ans1==ans2) puts("Yes");else puts("No");}}return 0; }

转载于:https://www.cnblogs.com/sbfhy/p/7676969.html

总结

以上是生活随笔为你收集整理的CodeForces 869E The Untended Antiquity 二维树状数组，随机hash的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。