POJ 2155 Matrix (D区段树)-白红宇

POJ 2155 Matrix (D区段树)

阅读量：4574 次

发布时间：2019-06-08

本文共 3446 字，大约阅读时间需要 11 分钟。

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

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

Sample Output

Source

,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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  #include
                   
                    #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 1007using 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
                    
                     >1; if (px

转载于:https://www.cnblogs.com/bhlsheji/p/4890312.html

你可能感兴趣的文章