POJ 2155 Matrix (二维树状数组)

本文主要是介绍POJ 2155 Matrix (二维树状数组)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给一个N*N的零一矩阵，每个操作询问某点的值或者翻转一个矩形区间。

思路：转换题目，新建A矩阵，A矩阵中每一点的值表示，以这一点为左下角的特殊矩形被翻转的次数，

然后用容斥原理把翻转一个矩形表示成翻转四个特殊矩形（以矩阵右边界和矩阵上边界为边界的矩形），

翻转矩形，就只需要把四个点的A矩阵值+1.

然后一个点的状态就要记录这个点被翻了多少次，也就是这个点左下角中的A矩阵值之和。

用二维树状数组维护这个和，就可以了。

//454MS  4060K 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,t,x;
int A[1002][1002];
void Add(int x,int y){while(x <= n){int yy=y; while(yy <= n){A[x][yy]++;yy+=yy&-yy; }x+=x&-x;}
}
int Sum(int x,int y){int ANS=0;while(x > 0){int yy=y;while(yy > 0){ANS+=A[x][yy];yy-=yy&-yy;}x-=x&-x;}return ANS;
}
int main(void)
{ scanf("%d",&x);while(x-->0){scanf("%d%d",&n,&t);memset(A,0,sizeof(A));for(int i=0;i<t;++i){char op;scanf(" %c",&op);if(op=='C'){int x1,x2,y1,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);//修改Add(x1,y1);Add(x2+1,y2+1);Add(x1,y2+1);Add(x2+1,y1);}else{int x,y;scanf("%d%d",&x,&y);//询问printf("%d\n",Sum(x,y)&1);} }printf("\n");}
return 0;
}

这篇关于POJ 2155 Matrix (二维树状数组)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---