poj 1195Mobile phones

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 1026
 5 using namespace std;
 6 
 7 int a[maxn][maxn];
 8 int c[maxn][maxn];
 9 int S,x,y,aa,l,r,b,t,h,T;
10 
11 int lowbit(int x)
12 {
13     return x&(x^(x-1));
14 }
15 
16 void update(int i,int j,int k)
17 {
18     while(i<=S)
19     {
20         int temp=j;
21         while(temp<=S)
22         {
23             c[i][temp]+=k;
24             temp+=lowbit(temp);
25         }
26         i+=lowbit(i);
27     }
28 }
29 
30 int sum(int i,int j)
31 {
32     int sum1=0;
33     while(i>0)
34     {
35         int temp=j;
36         while(temp>0)
37         {
38             sum1+=c[i][temp];
39             temp-=lowbit(temp);
40         }
41         i-=lowbit(i);
42     }
43     return sum1;
44 }
45 
46 int main()
47 {
48     while(scanf("%d",&h))
49     {
50         if(h==0)
51         {
52             scanf("%d",&S);
53             memset(c,0,sizeof(c));
54         }
55         else if(h==3) break;
56         else if(h==1)
57         {
58             scanf("%d%d%d",&x,&y,&aa);
59             update(x+1,y+1,aa);
60         }
61         else if(h==2)
62         {
63             scanf("%d%d%d%d",&l,&r,&b,&t);
64             int sum1=sum(b+1,t+1);
65             int sum2=sum(l,t+1);
66             int sum3=sum(b+1,r);
67             int sum4=sum(l,r);
68             printf("%d
",sum1-sum2-sum3+sum4);
69         }
70     }
71     return 0;
72 }
View Code