[HDU 1892] 2 차원 트 리 배열

제목 링크: http://acm.hdu.edu.cn/showproblem.php?pid=1892
제목 대의: 여러 칸 이 있 습 니 다. 각 칸 에 대응 하 는 좌 표 는 (I, J) 입 니 다. 처음에 칸 마다 책 이 한 권 씩 있 었 습 니 다. 그리고 한 구역 에 몇 권 의 책 이 있 는 지 통계 하 라 고 했 습 니 다. 그리고 책 을 늘 리 고 줄 이 며 책 을 이동 할 수 있 습 니 다.
문제 풀이 방향:
 1 차원 나무 모양 의 배열 과 다 르 지 않 습 니 다. 1 차원 은 2 차원 으로 확장 되 었 을 뿐 입 니 다.
 주의해 야 할 두 가 지 는 1. x, y 좌 표 는 0 에서 시작 하기 때문에 업 데 이 트 를 저장 할 때 좌 표 는 각각 1 을 추가 하여 업데이트 합 니 다. 0 좌 표 는 사순환 에 들 어가 기 때 문 입 니 다.
                          2. 구간 이 합 쳐 질 때 bit 배열 에 저 장 된 것 은 전체 왼쪽 아래 의 합 이 므 로 이 위 치 를 표시 하 는 수 를 조작 해 야 합 니 다.
 

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <algorithm>

 4 #include <cstring>

 5 using namespace std;

 6 

 7 const int maxn=1005;

 8 int  bit[maxn][maxn];

 9 

10 int lowbit(int x)

11 {

12     return x&(-x);

13 }

14 

15 void add(int x, int y, int val)

16 {

17     while(x<maxn)

18     {

19         int t=y;

20         while(t<maxn)

21         {

22             bit[x][t]+=val;

23             t+=lowbit(t);

24         }

25         x+=lowbit(x);

26     }

27 }

28 

29 int sum(int x, int y)

30 {

31     int ans=0;

32     while(x>0)

33     {

34         int t=y;

35         while(t>0)

36         {

37             ans+=bit[x][t];

38             t-=lowbit(t);

39         }

40         x-=lowbit(x);

41     }

42     return ans;

43 }

44 

45 int  find(int x,int y)

46 {

47     return sum(x,y)-sum(x-1,y)-sum(x,y-1)+sum(x-1,y-1);

48 }

49 

50 int main()

51 {

52     int  T, n, x1, x2, y1, y2, a, tcase=0;

53     char  ch[5];

54     cin >> T;

55     while(T--)

56     {

57         printf("Case %d:
",++tcase);

58         scanf("%d",&n);

59         memset(bit,0,sizeof(bit));

60         for(int i=1; i<maxn; i++)

61             for(int j=1; j<maxn; j++)

62                 add(i,j,1);

63         for(int i=0; i<n; i++)

64         {

65             scanf("%s",ch);

66             if(ch[0]=='A'||ch[0]=='D')

67             {

68                 scanf("%d%d%d",&x1,&y1,&a);

69                 if(ch[0]=='D')

70                        a=-min(a,find(x1+1,y1+1));

71                 add(x1+1,y1+1,a);

72             }

73             else if(ch[0]=='M')

74             {

75                 scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&a);

76                 int  tmp=min(a,find(x1+1,y1+1));

77                 add(x1+1,y1+1,-tmp);

78                 add(x2+1,y2+1,tmp);

79             }

80             else

81             {

82                 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

83                 if(x1>x2) swap(x1,x2);

84                 if(y1>y2) swap(y1,y2);

85                 int  tmp=sum(x2+1,y2+1)-sum(x1,y2+1)-sum(x2+1,y1)+sum(x1,y1);

86                 printf("%d
",tmp);

87             }

88         }

89     }

90     return 0;

91 }