poj 2155 Matrix
問題:
方法1:2 D線分ツリー.
方法2:一定の変換を経て、点修正、区間クエリーに変換し、パリティの問題を判断し、2次元ツリー配列を書くことができます.具体的には、09年の国家合宿チーム・武森の「情報学コンテストでの「0」と「1」の論文を見てみましょう
方法1:2 D線分ツリー.
方法2:一定の変換を経て、点修正、区間クエリーに変換し、パリティの問題を判断し、2次元ツリー配列を書くことができます.具体的には、09年の国家合宿チーム・武森の「情報学コンテストでの「0」と「1」の論文を見てみましょう
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long tree[1010][1010];
int n;
inline int lowbit(int x)
{
return x&(-x);
}
void add(int x,int y,long long c)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=n;j+=lowbit(j))
tree[i][j]+=c;
}
long long getsum(int x,int y)
{
long long sum=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
sum+=tree[i][j];
return sum;
}
int main()
{
int sec,t;
scanf("%d",&sec);
for(int z=1;z<=sec;z++)
{
memset(tree,0,sizeof(tree));
scanf("%d%d",&n,&t);
char s[10];
for(int p=1;p<=t;p++)
{
scanf("%s",s);
if(s[0]=='C')
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
add(x1,y1,1);
add(x2+1,y2+1,1);
add(x1,y2+1,1);
add(x2+1,y1,1);
}
else
{
int x,y;
scanf("%d%d",&x,&y);
printf("%I64d
",getsum(x,y)%2);
}
}
if(z<sec)printf("
");
}
return 0;
}