poj 2155 Matrix

1432 ワード

問題:
方法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; }