POJ 2155 Matrix

发布时间:2017-2-22 18:43:25 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ 2155 Matrix",主要涉及到POJ 2155 Matrix方面的内容,对于POJ 2155 Matrix感兴趣的同学可以参考一下。

二维树状数组。每个矩阵翻转后令从四个角为左上角到[n,n]为右下角矩阵+1或-1。以记录翻转次数。所有与要查询点有关的翻转都在当前点为右下角的矩阵中。求和模2即可求出结果。 #include<cstdio> #include<cstring> #include<iostream> using namespace std; #define N 1005 int n; int c[N][N]; int lowbit(int x) {     return x & (-x) ; } int sum(int x,int y) {     int sum = 0;     int x0 = x , y0 = y;     while(x > 0) {         y = y0;         while(y > 0) {             sum += c[x][y];             y -= lowbit(y);         }         x -= lowbit(x);     }     return sum; } void add(int x , int y , int d) {     int x0 = x , y0 = y;     while(x <= n) {         y = y0;         while(y <= n) {             c[x][y] += d;             y += lowbit(y);         }         x += lowbit(x);     } } int main() {     int num;     scanf("%d" , &num);     char ch;     int t;     while(num --) {         memset(c,0,sizeof(c));         scanf("%d%d" , &n , &t);         for(int i = 0 ; i < t ; i ++) {             getchar();             scanf("%c" , &ch);             if(ch == 'C') {                 int x1 , y1 , x2 , y2;                 scanf("%d%d%d%d" , &x1 , &y1 , &x2 , &y2);                 add (x2+1 , y2+1 , 1);                 add (x1 , y2+1 , -1);                 add (x2+1 , y1 , -1);                 add (x1 , y1 , 1);             }             else {                 int x , y;                 scanf("%d%d" , &x , &y);                 printf("%d\n" , (sum(x , y)&1));             }         }         printf("\n");     }     return 0; }

上一篇:
下一篇:舵机应用

相关文章

关键词: POJ 2155 Matrix

相关评论