Poj 1195 Mobile phones(2 Dツリー配列)

 1 #include <iostream>

 2 #include<cstring>

 3 #include<algorithm>

 4 #include<stdlib.h>

 5 #include<cstdio>

 6 using namespace std;

 7 #define N 1050

 8 #define lowbit(x) (x&(-x))

 9 int n,c[N][N];

10 void add(int i,int j,int da)

11 {

12     int k;

13     while(i<=n)

14     {

15         k = j;

16         while(k<=n)

17         {

18             c[i][k]+=da;

19             k+=lowbit(k);

20         }

21         i+=lowbit(i);

22     }

23 }

24 int getsum(int i,int j)

25 {

26     int sum=0,k;

27     while(i)

28     {

29         k = j;

30         while(k)

31         {

32             sum+=c[i][k];

33             k-=lowbit(k);

34         }

35         i-=lowbit(i);

36     }

37     return sum;

38 }

39 int main()

40 {

41     int k,a,b,cc,d,t;

42     cin>>t>>n;

43     memset(c,0,sizeof(c));

44     while(scanf("%d",&k),k!=3)

45     {

46         if(k==1)

47         {

48             scanf("%d%d%d",&a,&b,&cc);

49             add(a+1,b+1,cc);

50         }

51         else if(k==2)

52         {

53             scanf("%d%d%d%d",&a,&b,&cc,&d);

54             a++;b++;cc++;d++;

55             printf("%d
",getsum(cc,d)-getsum(a-1,d)-getsum(cc,b-1)+getsum(a-1,b-1));

56         }

57     }

58     return 0;

59 }