原題鏈接 題意：給定一個初始為0的矩陣，每次可以使一個方塊內(nèi)的數(shù)由0變成1或者由1變成0，詢問某一點是1還是0 思路：普通修改肯定過不了，但是有一點，某一個點如果被改變k次那么這個點就是k&1或者說k%2。基于這個思路，我們可以用樹狀數(shù)組方便地得出某一個點被修改過多少次。假設(shè)sum[i][j]可以求得i,j這個點被改變的次數(shù)，那么如果我們給出
12 2C 1 1 2 2Q 2 2這組數(shù)據(jù)，那么我們我們可以先讓sum[i][j]成為如下的樣子 x/y 1 2 3 4 1 1 1 1 1 2 1 1 1 1 3 1 1 1 1 4 1 1 1 1 接下來讓y>=3的部分全減去1 x/y 1 2 3 4 1 1 1 0 0 2 1 1 0 0 3 1 1 0 0 4 1 1 0 0 接下來讓x>=3的部分全減去1 x/y 1 2 3 4 1 1 1 0 0 2 1 1 0 0 3 0 0 -1 -1 4 0 0 -1 -1 接下來讓x>=3，y>=3的部分全加上1 x/y 1 2 3 4 1 1 1 0 0 2 1 1 0 0 3 0 0 0 0 4 0 0 0 0 這不就是我們想要的將左上角為(1,1)，右下角為(2,2)的部分全變成1的效果嗎？但是sum這個函數(shù)的結(jié)果是這個樣子，但是實際上對于用來存儲數(shù)據(jù)的bit數(shù)組卻不是這個樣子，它略有不同他是這個樣子的
1 1 0 1 1 1 0 1 0 0 0 0 1 1 0 1 1 1 -1 0 1 1 -1 0 0 0 0 0 1 1 -1 0 1 1 -1 0 1 1 -1 0 -1 -1 0 -1 0 0 -1 -1 1 1 -1 0 1 1 -1 0 -1 -1 1 0 0 0 0 0但是執(zhí)行對于樹狀數(shù)組的求和操作的時候出來的結(jié)果就是之前的那些矩陣了 代碼如下
#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int maxn = 1005;int bit[maxn][maxn];int K,n,m;int lowbit(int x){ return x & -x;}void add(int x,int y,int v){ for(int i=x;i<=10;i+=lowbit(i)) for(int j=y;j<=10;j+=lowbit(j)) bit[i][j]+=v;}int query(int x,int y){ int s; for(int i=x;i>0;i-=lowbit(i)) for(int j=y;j>0;j-=lowbit(j)) s += bit[i][j]; return s;}int main(){ cin >> K; while(K--){ cin >> n >> m; memset(bit,0,sizeof(bit)); while(m--){ char ch; cin >> ch; if(ch=='C'){ int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x2++;y2++; add(x1,y1,1); add(x1,y2,-1); add(x2,y1,-1); add(x2,y2,1); } else{ int x,y; scanf("%d%d",&x,&y); cout << (query(x,y)&1) << endl; } } cout << endl; }}新聞熱點
疑難解答
