Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 11018 | Accepted: 5044 |
Description
Input
Output
Sample Input
0 4
1 1 2 3
2 0 0 2 2
1 1 1 2
1 1 2 -1
2 1 1 2 3
3
Sample Output
3
4
Source
/*
POJ 1195 Mobile phones
二维树状数组
*/
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int MAXN=1030;
int c[MAXN][MAXN];
int n;
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int y,int val)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=n;j+=lowbit(j))
c[i][j]+=val;
}
int sum(int x,int y)
{
//if(x<=0||y<=0)return 0;
int s=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
s+=c[i][j];
return s;
}
int main()
{
int X,Y,A;
int L,B,R,T;
int t;
while(scanf("%d",&t)!=EOF)
{
scanf("%d",&n);
memset(c,0,sizeof(0));
while(scanf("%d",&t))
{
if(t==3)break;
else if(t==1)
{
scanf("%d%d%d",&X,&Y,&A);
add(X+1,Y+1,A);
}
else if(t==2)
{
scanf("%d%d%d%d",&L,&B,&R,&T);
printf("%d\n",sum(R+1,T+1)-sum(R+1,B)-sum(L,T+1)+sum(L,B));
}
}
}
return 0;
}
本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。