当前位置：首页 -> 基础 -> c++编程基础

POJ2155 Matrix 二维树状数组的应用

2014-11-24 12:14:44 · 作者: · 浏览: 1
标签: POJ2155 Matrix 二维 应用

有两种方法吧，一个是利用了树状数组的性质，很HDU1556有点类似，还有一种就是累加和然后看奇偶来判断答案


题意：给你一个n*n矩阵，然后q个操作，C代表把以(x1,y1)为左上角到以(x2，y2)为右下角的矩阵取反，意思就是矩阵只有0，1元素，是0的变1，是1的变0，Q代表当前(x,y)这个点的状况，是0还是1？


区间修改有点特别，但是若区间求和弄懂了应该马上就能懂得：

				add(x2,y2,1);//修改行小于等于x2,列小于等于y2的区域
				add(x2,y1,-1);//上面多修改了不需要的一部分，所以修改回来
				add(x1,y2,-1);//同上一步
				add(x1,y1,1);//往回多修改了一次 所以再正着修改一下

第一种方法，就是看一个点统计它左上角的矩阵元素和，看奇偶性，奇代表1，偶代表0，当然这种方法在区间修改的时候有点特殊，因为ADD函数修改的时候包括这个点以及它后面的，但是不能包括右下角的点，所以右下角的点坐标分别++即可 


#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define LL __int64 #define eps 1e-8 //const ll INF=9999999999999; #define inf 0xfffffff using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                  > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; int n; int c[1000 + 5][1000 + 5]; void clear() { memset(c,0,sizeof(c)); } int lowbit(int x) { return x&(-x); } void add(int x,int y,int value) { int i = y; while(x <= n) { y = i; while(y <= n) { c[x][y] += value; y += lowbit(y); } x += lowbit(x); } } int get_sum(int x,int y) { int sum = 0; int j = y; while(x > 0) { y = j; while(y > 0) { sum += c[x][y]; y -= lowbit(y); } x -= lowbit(x); } return sum; } int main() { int t; bool flag = false; scanf("%d",&t); while(t--) { if(flag)puts(""); else flag = true; clear(); int q; scanf("%d %d",&n,&q); char s[2]; while(q--) { scanf("%s",s); if(s[0] == 'C') { int x1,y1,x2,y2; scanf("%d %d %d %d",&x1,&y1,&x2,&y2); x2++,y2++; add(x2,y2,1);//修改行小于等于x2,列小于等于y2的区域 add(x2,y1,-1);//上面多修改了不需要的一部分，所以修改回来 add(x1,y2,-1);//同上一步 add(x1,y1,1);//往回多修改了一次 所以再正着修改一下 } else { int x,y; scanf("%d %d",&x,&y); int ans = get_sum(x,y); printf("%d\n",1&ans); } } } return 0; }

接下来的方法利用了树状数组的性质，在HDU1556的时候就有了两种做法，一个是+1修改然后-1修改，还有一个就是直接从大到小修改 从小到大求和，跟平时的反过来就可以了，这里也就是反过来，、

这里说一下性质：从小到大修改然后从大到小求和那么求的就是一段区间的和，若反过来从大到小修改然后从小到大求和那么求的就是一个点的值

当然区间修改部分也就不需要特别处理了，跟平时一样处理即可

				add(x2,y2,1);//修改行小于等于x2,列小于等于y2的区域
				add(x2,y1 - 1,-1);//上面多修改了不需要的一部分，所以修改回来
				add(x1 - 1,y2,-1);//同上一步
				add(x1 - 1,y1 - 1,1);//往回多修改了一次 所以再正着修改一下


#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define LL __int64 #define eps 1e-8 //const ll INF=9999999999999; #define inf 0xfffffff using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                  > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; int n; int c[1000 + 5][1000 + 5]; void clear() { memset(c,0,sizeof(c)); } int lowbit(int x) { return x&(-x); } void add(int x,int y,int value) { int i = x; while(y > 0) { x = i; while(x > 0) { c[x][y] += value; x -= lowbit(x); } y -= lowbit(y); } } int get_sum(int x,int y) { int sum = 0; int j = x; while(y <= n) { x = j; while(x <= n) { sum += c[x][y]; x += lowbit(x); } y += lowbit(y); } return sum; } int main() { int t; bool flag = false; scanf("%d",&t); while(t--) { if(flag)puts(""); else flag = true; clear(); int q; scanf("%d %d",&n,&q); char s[2]; while(q--) { scanf("%s",s); if(s[0] == 'C') { int x1,y1,x2,y2; scanf("%d %d %d %d",&x1,&y1,&x2,&y2); add(x2,y2,1);//修改行小于等于x2,列小于等于y2的区域 add(x2,y1 - 1,-1);//上面多修改了不需要的一部分，所以修改回来 add(x1 - 1,y2,-1);//同上一步 add(x1 - 1,y1 - 1,1);//往回多修改了一次 所以再正着修改一下 } else { int x,y; scanf("%d %d",&x,&y); int ans = get_sum(x,y); printf("%d\n",1&ans); } } } return 0; }