首页 > 代码库 > POJ 2155 Matrix (二维线段树)

POJ 2155 Matrix (二维线段树)

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

Matrix
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 18143 Accepted: 6813

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


谨以此题来祭我的第一道二维线段树!

没有30道线段树的基础不要碰二维线段树!

题意:

给出一个N×N的零矩阵,有两种操作:C x1 y1 x2 y2 是将(x1,y1) (x2,y2)对应范围内的矩阵中的0/1互换,Q x y是查询(x,y)位置元素的值。

分析:

0/1互换即异或操作,朴素的算法时间复杂度显然不够。如果是一维的坐标轴显然可以用线段树解,但这是一个二维的,那么就要用到二维线段树了。

曾经的我天真地认为二维线段树就是把一个矩形直接分成4份:左上、右上、左下、右下,后来遇到一个三维的题目我还YY出了把立方体分成8份来解(当然没过啦,而且标程也不是用线段树的)。 实际上,二维线段树是先将X坐标二分,然后再将Y轴二分。第二维维护的也是一棵线段树,没错,二维线段树就是线段树套线段树!二分,再二分!

本题每次更新的时候先操作X轴,操作到对应区间时再对Y轴进行操作,从二维到一维,达到降维的效果。

查询时每次查到在所在的X区间内时都要对Y轴进行查询。

如果对线段树理解较深,相信对此不难理解。


详情请见代码(个人习惯维护左闭右开的区间,下标从0开始,所以有些调整):

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<cctype>
#include<cmath>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<map>
#include<set>
#define sqr(x) ((x)*(x))
#define LL long long
#define itn int
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
#define eps 1e-10
#define maxm
#define maxn 1007

using namespace std;

int XOR[maxn<<2][maxn<<2];
int n,m;

//update_1d() 更新一维
//[a,b)表示当前在一维操作的区间(Y方向),k为节点标号,[l,r)表示节点对应维护的区间(Y方向),k_2d表示二维对应的节点标号
void update_1d(int a,int b,int k,int l,int r,int k_2d)
{
    if (b<=l || r<=a)   return ;
    if (a<=l && r<=b)
    {
        XOR[k_2d][k]^=1;
    }
    else
    {
        update_1d(a,b,k*2+1,l,l+r>>1,k_2d);
        update_1d(a,b,k*2+2,l+r>>1,r,k_2d);
    }
}

//update_2d() 更新二维
//[a,b)表示当前在二维操作的区间(X方向),[y1,y2)表示将要在一维操作的区间(Y方向),k为节点标号,[l,r)表示节点对应维护的区间(X方向)
void update_2d(int a,int b,int y1,int y2,int k,int l,int r)
{
    if (b<=l || r<=a)   return ;
    if (a<=l && r<=b)
    {
        update_1d(y1,y2,0,0,n,k);
    }
    else
    {
        update_2d(a,b,y1,y2,k*2+1,l,l+r>>1);
        update_2d(a,b,y1,y2,k*2+2,l+r>>1,r);
    }
}

//query_1d() 查询一维
//p表示当前在一维查询的位置(Y方向),k为节点标号,[l,r)表示节点对应维护的区间(Y方向),k_2d表示二维对应的节点标号
int query_1d(int p,int k,int l,int r,int k_2d)
{
    if (r-l==1) return XOR[k_2d][k];

    int m=l+r>>1;

    if (p<m)
        return XOR[k_2d][k]^query_1d(p,k*2+1,l,m,k_2d);
    else
        return XOR[k_2d][k]^query_1d(p,k*2+2,m,r,k_2d);
}

//query_2d() 查询二维
//px表示当前在二维查询的位置(X方向),py表示将要在一维查询的位置(Y方向),k为节点标号,[l,r)表示节点对应维护的区间(X方向)
int query_2d(int px,int py,int k,int l,int r)
{
    int res=query_1d(py,0,0,n,k);// attention please!

    if (r-l==1) return res;

    int m=l+r>>1;

    if (px<m)
        return res^query_2d(px,py,k*2+1,l,m);
    else
        return res^query_2d(px,py,k*2+2,m,r);
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("/home/fcbruce/文档/code/t","r",stdin);
    #endif // ONLINE_JUDGE

    int T_T;
    scanf("%d",&T_T);


    while (T_T--)
    {

        scanf("%d %d",&n,&m);
        memset(XOR,0,sizeof XOR);

        for (int i=0;i<m;i++)
        {
            char op;
            int x1,x2,y1,y2;

            getchar();
            op=getchar();

            if (op=='C')
            {
                scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
                x1--;y1--;
                update_2d(x1,x2,y1,y2,0,0,n);
            }
            else
            {
                scanf("%d %d",&x1,&y1);
                x1--;y1--;
                printf("%d\n",query_2d(x1,y1,0,0,n));
            }
        }

        if (T_T)    putchar('\n');  //因为这个PE一发
    }



    return 0;
}