POJ 2155-Matrix（二维树状数组-区间修改单点查询）

墨蓝 2022-06-16 03:57 219阅读 0赞

Matrix

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;3000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;27355</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;10003</td> 
  </tr> 
 </tbody> 
</table>

Description

Given an N\*N matrix A, whose elements are either 0 or 1. A\[i, j\] means the number in the i-th row and j-th column. Initially we have A\[i, j\] = 0 (1 <= i, j <= N).  
  
We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using "not" operation (if it is a '0' then change it into '1' otherwise change it into '0'). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.  
  
1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2).  
2. Q x y (1 <= x, y <= n) querys A\[x, y\].

Input

The first line of the input is an integer X (X <= 10) representing the number of test cases. The following X blocks each represents a test case.  
  
The first line of each block contains two numbers N and T (2 <= N <= 1000, 1 <= T <= 50000) representing the size of the matrix and the number of the instructions. The following T lines each represents an instruction having the format "Q x y" or "C x1 y1 x2 y2", which has been described above.

Output

For each querying output one line, which has an integer representing A\[x, y\].  
  
There is a blank line between every two continuous test cases.

Sample Input

1
    2 10
    C 2 1 2 2
    Q 2 2
    C 2 1 2 1
    Q 1 1
    C 1 1 2 1
    C 1 2 1 2
    C 1 1 2 2
    Q 1 1
    C 1 1 2 1
    Q 2 1

Sample Output

1
    0
    0
    1

Source

[POJ Monthly][],Lou Tiancheng

##    题目意思： ##

N×N的矩形，元素值只能是0/1。

C X1 Y1 X2 Y2表示将左上角(X1,Y1)和右下角(X2,Y2)构成的矩形内的所有元素值取反；

Q X Y表示查询点(X,Y)处的元素值。

## 解题思路： ##

二位树状数组。

我们往往单点修改，区间查询，此时update是从小到大，getsum是从大到小；

现在要求区间修改，单点查询，所以update是从大到小，getsum是从小到大。

#include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    #define MAXN 1100
    int c[MAXN][MAXN],n;
    int lowbit(int x)
    {
        return x&(-x);
    }
    void update(int x,int y,int num)//从大到小修改
    {
        for(int i=x; i>0; i-=lowbit(i))
            for(int j=y; j>0; j-=lowbit(j))
                c[i][j]+=num;
    }
    int sum(int x,int y)//从小到大求和
    {
        int res=0;
        for(int i=x; i<=n; i+=lowbit(i))
            for(int j=y; j<=n; j+=lowbit(j))
                res+=c[i][j];
        return res;
    }
    
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
        //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        int T;
        scanf("%d",&T);
        while(T--)
        {
            int t;
            char op[2];
            memset(c,0,sizeof(c));
            scanf("%d%d",&n,&t);
            while(t--)
            {
                scanf("%s",op);
                if(op[0]=='C')
                {
                    int x1,y1,x2,y2;
                    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                    update(x1-1,y1-1,1);
                    update(x2,y2,1);
                    update(x1-1,y2,-1);
                    update(x2,y1-1,-1);
                }
                else if(op[0]=='Q')
                {
                    int x,y;
                    scanf("%d%d",&x,&y);
                    printf("%d\n",sum(x,y)%2);
                }
            }
            printf("\n");
        }
        return 0;
    }

[POJ Monthly]: http://poj.org/searchproblem?field=source&key=POJ+Monthly