首页 > 代码库 > POJ 2155 Matrix 二维树状数组
POJ 2155 Matrix 二维树状数组
题目大意:有一个全零的矩阵,有两个操作。
1.修改(x1,y1)到(x2,y2)的数,使它们取异或。
2.查询(x,y)的状态。
思路:二维树状数组,区间修改,单点查询。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 1010 using namespace std; int cases; int cnt,asks; bool arr_tree[MAX][MAX]; char s[10]; inline void Fix(int x,int y); inline bool GetSum(int x,int y); int main() { for(cin >> cases;cases; --cases) { memset(arr_tree,false,sizeof(arr_tree)); scanf("%d%d",&cnt,&asks); for(int i = 1;i <= asks; ++i) { scanf("%s",s); if(s[0] == 'C') { int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); Fix(x2,y2),Fix(x1 - 1,y1 - 1); Fix(x2,y1 - 1),Fix(x1 - 1,y2); } else { int x,y; scanf("%d%d",&x,&y); printf("%d\n",GetSum(x,y)); } } puts(""); } return 0; } inline void Fix(int x,int y) { for(int i = x;i;i -= i&-i) for(int j = y;j;j -= j&-j) arr_tree[i][j] ^= 1; } inline bool GetSum(int x,int y) { bool re = 0; for(int i = x;i <= cnt;i += i&-i) for(int j = y;j <= cnt;j += j&-j) re ^= arr_tree[i][j]; return re; }
POJ 2155 Matrix 二维树状数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。