poj 2155 Matrix(树状数组的应用)
来源：程序员人生 发布时间：2014-10-03 08:00:01 阅读次数：2826次
http://poj.org/problem?id=2155
对于一个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 <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
