国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > 互联网 > poj 2155 Matrix(树状数组的应用)

poj 2155 Matrix(树状数组的应用)

来源:程序员人生   发布时间:2014-10-03 08:00:01 阅读次数:2840次

http://poj.org/problem?id=2155


对于一个n*n(n <= 1000)的01矩阵,初始全为0,有两种操作。

C x1 y1 x2 y2 ,分别代表矩阵的左上角和右下角,将这个矩阵中的01互换,原为0的变为1,原为1的变为0。

Q x y询问A[x,y]现在是几。


因为只有01的互换,且原始为0,那么只需计算[x,y]处被换了几次就能确定现在这个格子是几。重点就是怎样快速计算[x,y]格子被换了几次。操作方法是将[x1,y1][x1,y2+1][x2+1,y1][x2+1,y2+1]格子出增加1,对于[x,y]只需求[1,1]到[x,y]的和就是[x,y]出被换了几次。


若转化成一维的,感觉和多校的一道题挺像,hdu 4970

详解 


#include <stdio.h> #include <iostream> #include <map> #include <set> #include <bitset> #include <list> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL __int64 //#define LL long long #define eps 1e-9 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int mod = 10000007; int c[1010][1010]; int n,m; int Lowbit(int x) { return x&(-x); } void update(int x,int y, int add) { while(x <= n) { int tmp = y; while(tmp <= n) { c[x][tmp] += add; tmp += Lowbit(tmp); } x += Lowbit(x); } } int sum(int x, int y) { int s = 0; while(x >= 1) { int tmp = y; while(tmp >= 1) { s += c[x][tmp]; tmp -= Lowbit(tmp); } x -= Lowbit(x); } return s; } int main() { int test; int x1,y1,x2,y2; scanf("%d",&test); while(test--) { char ch[2]; memset(c,0,sizeof(c)); scanf("%d %d",&n,&m); while(m--) { scanf("%s",ch); if(ch[0] == 'C') { scanf("%d %d %d %d",&x1,&y1,&x2,&y2); update(x1,y1,1); update(x1,y2+1,1); update(x2+1,y1,1); update(x2+1,y2+1,1); } else { scanf("%d %d",&x1,&y1); int s = sum(x1,y1); if(s&1) printf("1 "); else printf("0 "); } } printf(" "); } return 0; }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生