poj 2155 Matrix(樹狀數組的應用)
來源：程序員人生 發布時間：2014-10-03 08:00:01 閱讀次數：2989次
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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
