程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ2155 Matrix 二維樹狀數組的應用

POJ2155 Matrix 二維樹狀數組的應用

編輯：C++入門知識

有兩種方法吧，一個是利用了樹狀數組的性質，很HDU1556有點類似，還有一種就是累加和然後看奇偶來判斷答案

題意：給你一個n*n矩陣，然後q個操作，C代表把以(x1,y1)為左上角到以(x2，y2)為右下角的矩陣取反，意思就是矩陣只有0，1元素，是0的變1，是1的變0，Q代表當前(x,y)這個點的狀況，是0還是1？

區間修改有點特別，但是若區間求和弄懂了應該馬上就能懂得：

				add(x2,y2,1);//修改行小於等於x2,列小於等於y2的區域
				add(x2,y1,-1);//上面多修改了不需要的一部分，所以修改回來
				add(x1,y2,-1);//同上一步
				add(x1,y1,1);//往回多修改了一次 所以再正著修改一下

第一種方法，就是看一個點統計它左上角的矩陣元素和，看奇偶性，奇代表1，偶代表0，當然這種方法在區間修改的時候有點特殊，因為ADD函數修改的時候包括這個點以及它後面的，但是不能包括右下角的點，所以右下角的點坐標分別++即可

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long
#define LL __int64
#define eps 1e-8

//const ll INF=9999999999999;

#define inf 0xfffffff

using namespace std;


//vector > G;
//typedef pair P;
//vector> ::iterator iter;
//
//mapmp;
//map::iterator p;


int n;

int c[1000 + 5][1000 + 5];

void clear() {
	memset(c,0,sizeof(c));
}

int lowbit(int x) {
	return x&(-x);
}

void add(int x,int y,int value) {
	int i = y;
	while(x <= n) {
		y = i;
		while(y <= n) {
			c[x][y] += value;
			y += lowbit(y);
		}
		x += lowbit(x);
	}
}

int get_sum(int x,int y) {
	int sum = 0;
	int j = y;
	while(x > 0) {
		y = j;
		while(y > 0) {
			sum += c[x][y];
			y -= lowbit(y);
		}
		x -= lowbit(x);
	}
	return sum;
}

int main() {
	int t;
	bool flag = false;
	scanf("%d",&t);
	while(t--) {
		if(flag)puts("");
		else flag = true;
		clear();
		int q;
		scanf("%d %d",&n,&q);
		char s[2];
		while(q--) {
			scanf("%s",s);
			if(s[0] == 'C') {
				int x1,y1,x2,y2;
				scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
				x2++,y2++;
				add(x2,y2,1);//修改行小於等於x2,列小於等於y2的區域
				add(x2,y1,-1);//上面多修改了不需要的一部分，所以修改回來
				add(x1,y2,-1);//同上一步
				add(x1,y1,1);//往回多修改了一次 所以再正著修改一下
			}
			else {
				int x,y;

				scanf("%d %d",&x,&y);
				int ans = get_sum(x,y);
				printf("%d\n",1&ans);
			}
		}
	}
	return 0;
}

接下來的方法利用了樹狀數組的性質，在HDU1556的時候就有了兩種做法，一個是+1修改然後-1修改，還有一個就是直接從大到小修改從小到大求和，跟平時的反過來就可以了，這裡也就是反過來，、

這裡說一下性質：從小到大修改然後從大到小求和那麼求的就是一段區間的和，若反過來從大到小修改然後從小到大求和那麼求的就是一個點的值

當然區間修改部分也就不需要特別處理了，跟平時一樣處理即可

				add(x2,y2,1);//修改行小於等於x2,列小於等於y2的區域
				add(x2,y1 - 1,-1);//上面多修改了不需要的一部分，所以修改回來
				add(x1 - 1,y2,-1);//同上一步
				add(x1 - 1,y1 - 1,1);//往回多修改了一次 所以再正著修改一下

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long
#define LL __int64
#define eps 1e-8

//const ll INF=9999999999999;

#define inf 0xfffffff

using namespace std;


//vector > G;
//typedef pair P;
//vector> ::iterator iter;
//
//mapmp;
//map::iterator p;


int n;

int c[1000 + 5][1000 + 5];

void clear() {
	memset(c,0,sizeof(c));
}

int lowbit(int x) {
	return x&(-x);
}

void add(int x,int y,int value) {
	int i = x;
	while(y > 0) {
		x = i;
		while(x > 0) {
			c[x][y] += value;
			x -= lowbit(x);
		}
		y -= lowbit(y);
	}
}

int get_sum(int x,int y) {
	int sum = 0;
	int j = x;
	while(y <= n) {
		x = j;
		while(x <= n) {
			sum += c[x][y];
			x += lowbit(x);
		}
		y += lowbit(y);
	}
	return sum;
}

int main() {
	int t;
	bool flag = false;
	scanf("%d",&t);
	while(t--) {
		if(flag)puts("");
		else flag = true;
		clear();
		int q;
		scanf("%d %d",&n,&q);
		char s[2];
		while(q--) {
			scanf("%s",s);
			if(s[0] == 'C') {
				int x1,y1,x2,y2;
				scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
				add(x2,y2,1);//修改行小於等於x2,列小於等於y2的區域
				add(x2,y1 - 1,-1);//上面多修改了不需要的一部分，所以修改回來
				add(x1 - 1,y2,-1);//同上一步
				add(x1 - 1,y1 - 1,1);//往回多修改了一次 所以再正著修改一下
			}
			else {
				int x,y;
				scanf("%d %d",&x,&y);
				int ans = get_sum(x,y);
				printf("%d\n",1&ans);
			}
		}
	}
	return 0;
}