Poj 1195 Mobile phones(2 Dツリー配列ベース)
1294 ワード
http://poj.org/problem?id=1195
題意:s*sの四角形があり、ある四角形a[x][y]に1つの数addを加え、あるサブマトリクス内のすべての数字の和を尋ねる2つの操作がある.
考え方:2 Dツリー配列のテンプレート.なお,タイトルの下付き文字は0から,樹状配列の下付き文字は1からであるため,下付き文字はいずれも右に1桁シフトする.
題意:s*sの四角形があり、ある四角形a[x][y]に1つの数addを加え、あるサブマトリクス内のすべての数字の和を尋ねる2つの操作がある.
考え方:2 Dツリー配列のテンプレート.なお,タイトルの下付き文字は0から,樹状配列の下付き文字は1からであるため,下付き文字はいずれも右に1桁シフトする.
#include <stdio.h>
#include <string.h>
const int maxn = 1030;
int Lowbit(int x)
{
return x&(-x);
}
int c[maxn][maxn];
int n;
// a[i][j] add;
void update(int i, int j, int add)
{
while(i <= n)
{
int tmp = j;
while(tmp <= n)
{
c[i][tmp] += add;
tmp += Lowbit(tmp);
}
i += Lowbit(i);
}
}
//a[1][1]~a[i][j] ( )
int sum(int i, int j)
{
int s = 0;
while(i > 0)
{
int tmp = j;
while(tmp > 0)
{
s += c[i][tmp];
tmp -= Lowbit(tmp);
}
i -= Lowbit(i);
}
return s;
}
int main()
{
int f;
int x,y,add;
int l,r,b,t;
memset(c,0,sizeof(c));
while(1)
{
scanf("%d",&f);
if(f == 0)
scanf("%d",&n);
else if(f == 1)
{
scanf("%d %d %d",&x,&y,&add);
update(x+1,y+1,add);
}
else if(f == 2)
{
scanf("%d %d %d %d",&l,&b,&r,&t);
l++;// ,
r++;
b++;
t++;
int ans = sum(r,t)-sum(l-1,t)-sum(r,b-1)+sum(l-1,b-1);
printf("%d
",ans);
}
else if(f == 3)
break;
}
return 0;
}