POJ2155【二维树状数组，区间修改，点查询？】【又被输入输出坑】

这题反反复复，到现在才过。

这道题就是树状数组的逆用，用于修改区间内容，查询点的值。

如果单纯就这个奇偶数来判的话，似乎这个思路比较好理解。

看了一下国家集训队论文（囧），《关于0与1在信息学奥赛中的运用》，。

还有这题卡在输入输出好久。

update(a,b,1);
update(a,d,-1);
update(c,b,-1);
update(c,d,1);

 用来判二维的情况！！

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

//关键还是对树状数组理解比较深，差不多算是知晓了。

//区间修改，点查询

int a[1005];

int c[1005][1005];

int n,m;

int lowbit(int x)

{

    return x&(-x);

}

void update(int x,int y,int pp)

{

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

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

           c[i][j]+=pp;

}

int sum(int x,int y)

{

    int ret=0;

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

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

           ret+=c[i][j];

    return ret;

}

int main()

{

    int case_num;

    scanf("%d",&case_num);

    while(case_num--)

    {

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

        scanf("%d%d%*c",&n,&m);

        for(int i=0;i<m;i++)

        {

            char op;

            int a,b,c,d;

            scanf("%c",&op);

            if(op=='C')

            {

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

              c++;

              d++;

              update(a,b,1);//这个思路要比我那个几各情况If判断要好

              update(a,d,-1);

              update(c,b,-1);

              update(c,d,1);

            }

            else if(op=='Q')

            {

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

                printf("%d\n",1&sum(a,b));

            }

        }

        printf("\n");

    }

    return 0;

}

POJ2155【二维树状数组，区间修改，点查询？】【又被输入输出坑】的相关教程结束。