poj 2155 Matrix(树状数组的应用) - c++编程基础

TOP

poj 2155 Matrix(树状数组的应用)

2015-07-20 17:36:26 来源: 作者: 【大中小】浏览:3次

对于一个n*n（n <= 1000）的01矩阵，初始全为0，有两种操作。

C x1 y1 x2 y2 ，分别代表矩阵的左上角和右下角，将这个矩阵中的01互换，原为0的变为1，原为1的变为0。

Q x y询问A[x,y]现在是几。

因为只有01的互换，且原始为0，那么只需计算[x,y]处被换了几次就能确定现在这个格子是几。重点就是怎样快速计算[x,y]格子被换了几次。操作方法是将[x1,y1][x1,y2+1][x2+1,y1][x2+1,y2+1]格子出增加1，对于[x,y]只需求[1,1]到[x,y]的和就是[x,y]出被换了几次。

若转化成一维的，感觉和多校的一道题挺像，hdu 4970

详解

#include 
  
   
#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #define LL __int64 //#define LL long long #define eps 1e-9 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int mod = 10000007; int c[1010][1010]; int n,m; int Lowbit(int x) { return x&(-x); } void update(int x,int y, int add) { while(x <= n) { int tmp = y; while(tmp <= n) { c[x][tmp] += add; tmp += Lowbit(tmp); } x += Lowbit(x); } } int sum(int x, int y) { int s = 0; while(x >= 1) { int tmp = y; while(tmp >= 1) { s += c[x][tmp]; tmp -= Lowbit(tmp); } x -= Lowbit(x); } return s; } int main() { int test; int x1,y1,x2,y2; scanf(%d,&test); while(test--) { char ch[2]; memset(c,0,sizeof(c)); scanf(%d %d,&n,&m); while(m--) { scanf(%s,ch); if(ch[0] == 'C') { scanf(%d %d %d %d,&x1,&y1,&x2,&y2); update(x1,y1,1); update(x1,y2+1,1); update(x2+1,y1,1); update(x2+1,y2+1,1); } else { scanf(%d %d,&x1,&y1); int s = sum(x1,y1); if(s&1) printf(1 ); else printf(0 ); } } printf( ); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 1830(高斯消元)	下一篇：HDU4027Can you answer these que..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: