CodeForces 869E

題意： n*m 的格子，有三種操作， 1、在一個(gè)矩形周圍加一層障礙。2、把一個(gè)矩形周圍的障礙去掉。 3、詢問兩個(gè)格子是否可達(dá)。???? 題目保證不會(huì)有矩形障礙交叉，且去掉的矩形一定是在前面已給出的。

tags：

知道二維樹狀數(shù)組的話應(yīng)該很容易想到怎么做，增減矩形只要給矩形里面的格子打上這個(gè)矩形的標(biāo)記，詢問的時(shí)候就看兩個(gè)格子的標(biāo)記是否一樣即可。

但這題難在給矩形一個(gè)hash值，必須要保證兩個(gè)被不同矩形圍著的格子上標(biāo)記的hash值不一樣，這其實(shí)不太可能一定保證，只能讓概率盡可能小。

我們可以隨機(jī)給出矩形的 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; }

轉(zhuǎn)載于:https://www.cnblogs.com/sbfhy/p/7676969.html

總結(jié)

以上是生活随笔為你收集整理的CodeForces 869E The Untended Antiquity 二维树状数组，随机hash的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。