poj2155Matrix

Description

Input

Output

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

题意是给你个矩阵里面开始全是0，然后给你两种指令：1：‘C x1,y1,x2,y2’就是将左上角为x1,y1,右下角为x2,y2,的这个矩阵内的数字全部翻转，0变1,1变0,；2:‘Q x1 y1‘,输出a[x1][y1]的值。

二维树状数组：对于一个矩阵,迅速修改其一个点的值,迅速求其左上角连续子矩阵的和

#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<list>
#include<iomanip>
#include<stack>
#include<set>
using namespace std;
int bit[1010][1010],n;
void update(int r,int c,int val)
{
	for(int i=r;i<=n;i+=i&-i)
		for(int j=c;j<=n;j+=j&-j)
			bit[i][j]+=val;
}
int psum(int r,int c)
{
	int ans=0;
	for(int i=r;i>0;i-=i&-i)
		for(int j=c;j>0;j-=j&-j)
			ans+=bit[i][j];
	return ans;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int m;
		scanf("%d%d",&n,&m);
		memset(bit,0,sizeof(bit));
		while(m--)
		{
			char s[100];
			scanf("%s",s);
			if(s[0]=='C')
			{
				int r1,c1,r2,c2;
				scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
				update(r1,c1,1);
				update(r1,c2+1,-1);
				update(r2+1,c1,-1);
				update(r2+1,c2+1,1);
			}
			else
			{
				int r,c;
				scanf("%d%d",&r,&c);
				printf("%d\n",psum(r,c)%2);
			}
		}
		puts("");
	}
}

poj2155Matrix

原文：http://blog.csdn.net/stl112514/article/details/45311497