Matrix

1690 ワード

poj 2155
第1行はテスト用例の回数を与えて、第2行は第1はマトリックスのsizeを与えて、第2は命令の個数を与えます
Cは更新データを表し、x 1<=x<=x 2の範囲と、y 1<=y<=y 2の範囲内の数にそれぞれ1を加え、Qはある点を尋ねる大きさを表す
解決:2 Dツリー配列はpoj 1195 mobile phonesとは正反対で、挿入領域です.
#include <iostream> 

#include <cstdio>

#include <cstring>

using namespace std;

const int N=1010;

int c[N][N];

void init()

{

    memset(c,0,sizeof(c));

}

int n;

int lowbit(int x)

{

    return x&(-x);

}

void updata(int x,int y,int inc)

{

    for(int i=x;i>0;i-=lowbit(i))

      for(int j=y;j>0;j-=lowbit(j))

       c[i][j]+=inc;

}

int get(int x,int y)

{

    int sum=0;

    for(int i=x;i<=n;i+=lowbit(i))

      for(int j=y;j<=n;j+=lowbit(j))

        sum+=c[i][j];

     return  sum%2;  

}

int main()

{

    int t,icase;

    char cmd;

    int a,b,c,d;

    scanf("%d",&icase);

    while(icase--)

    {

        init();

        scanf("%d%d",&n,&t);

        while(t--)

        {

            getchar();

            scanf("%c",&cmd);

            if(cmd=='C')

            {

                scanf("%d%d%d%d",&a,&b,&c,&d);

                updata(c,d,1);

                updata(a-1,b-1,1);

                updata(c,b-1,-1);

                updata(a-1,d,-1);

            }

            else 

            { 

                scanf("%d%d",&a,&b);

                printf("%d
",get(a,b)); } } printf("
"); } system("pause"); return 0; }