现在的位置: 首页 > 算法 > 正文

poj2155

2017年11月23日 算法 ⁄ 共 1061字 ⁄ 字号 评论关闭

题意:给了一个初始值全部为0的数组,有两种指令,C和Q,C是更改(x1,y1)到(x2,y2)范围内的数值,如果是0则改为1,如果是1则改为0。【题目称之为翻转】,Q是查询(x,y)的数值。

这是一个二维数组的区间更新和单点查询的题目,sum和update方法相对于一维的树状数组增加了一个循环。需要注意的地方是,树状数组只能更新(1,1)到(x,y)的数值,所以在更新(x1,y1)到(x2,y2)范围内时,先翻转(1,1)到(x2,y2)范围内,再将除去(x1,y1)和(x2,y2)的范围再翻转一次。c数组用来记录的是翻转次数。该位置的数值就是该位置c数组的数值mode2。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int c[1005][1005],n;
int lowbit(int i)
{
    return i&(-i);
}
int sum(int x,int y)
{

   int ans=0;
    for(int i=x;i>0;i-=lowbit(i))
        for(int j=y;j>0;j-=lowbit(j))
        {
            ans+=c[i][j];
        }
        return ans;
}
void update(int x,int y,int k)
{
  for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=n;j+=lowbit(j))
        {
            c[i][j]+=k;
        }

}
int main()
{

    int casen,t;
    scanf("%d",&casen);
    while(casen--)
    {
        memset(c,0,sizeof(c));
        scanf("%d%d",&n,&t);
        getchar();
        for(int i=0;i<t;i++)
        {
            int x1,y1,x2,y2;
            char ch;

            scanf("%c",&ch);
            if(ch=='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);
                getchar();
            }
            else
            {
                int a,b;
                scanf("%d%d",&a,&b);
                getchar();
                printf("%d\n",sum(a,b)%2);
            }


        }
        printf("\n");
    }
}

这题我被挂了一个多小时。。就因为sum方法中更新j的时候lowbit传的参数是i,这些错误要杜绝掉的啊嘞。。。。。真是。。。浪费好久

抱歉!评论已关闭.