Posted on 2010-10-29 15:05
acronix 阅读(305)
评论(0) 编辑 收藏 引用 所属分类:
hzshuai解题报告
题意：给一个二维矩阵，边修改点格的手机的改变数目，边查询区间手机的总数目。
分析：就是Matrix的相反操作。
CPP代码：
#include <iostream>
#include <cstdio>
using namespace std;
int n;
int c[1030][1030];
int Lowbit(int i)
{
return i&(-i);
}
void up(int x,int y,int a)
{
int i = x,j;
while (i <= n)
{
j = y;
while (j <= n)
{
c[i][j] += a;
j += Lowbit(j);
}
i += Lowbit(i);
}
}
int down(int x,int y)
{
int i = x,j,res = 0;
while (i > 0)
{
j = y;
while (j > 0)
{
res += c[i][j];
j -= Lowbit(j);
}
i -= Lowbit(i);
}
return res;
}
int main()
{
int ins,x,y,x1,y1,a;
int i,j;
scanf("%d %d",&ins,&n);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
c[i][j] = 0;
while (1)
{
scanf("%d",&ins);
if (ins == 3)
break;
if (ins == 1)
{
scanf("%d %d %d",&x,&y,&a);
x++,y++;
up(x,y,a);
}
if (ins == 2)
{
int ans = 0;;
scanf("%d %d %d %d",&x,&y,&x1,&y1);
x++,y++,x1++,y1++;
ans = down(x1,y1) - down(x1,y-1) - down(x-1,y1) + down(x-1,y-1);
printf("%d\n",ans);
}
}
return 0;
}