POJ 1195 - Mobile phones

http://poj.org/problem?id=1195

概要

行列について，以下の命令を処理する

• 0 S
  • S * S の行列のすべての要素を 0 で初期化する
• 1 X Y A
  • (X, Y) の要素の値に A を足す (A は負の値も取り得る)
• 2 L B R T
  • L <= X <= R, B <= Y <= T なるすべての (X, Y) の要素の和を答える
• 3
  • 終了する

制約

• 1 <= S <= 1024
• 各要素の値 V: 0 <= V <= 32767
• -32768 <= A <= 32767
• 処理の途中で V が負になるような A はこない
• 命令の数 U: 3 <= U <= 60002
• 行列全体の要素の和 M: M <= 2^30

解法

二次元の BinaryIndexedTree． ちなみに一次元の BinaryIndexedTree の配列でも 4047MS で通った．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 static const int MAXX = 1<<10, MAXY = 1<<10;
 5 
 6 template <class T>
 7 struct BinaryIndexedTree2
 8 {
 9   T tree[MAXX+1][MAXY+1];
10   int X, Y;
11 
12   T read(int x, int y) const
13   {
14     T sum = 0;
15     while (x > 0) {
16       sum += read_(x, y);
17       x -= x & -x;
18     }
19     return sum;
20   }
21 
22   T read_(int x, int y) const
23   {
24     T sum = 0;
25     while (y > 0) {
26       sum += tree[x][y];
27       y -= y & -y;
28     }
29     return sum;
30   }
31 
32   void add(int x, int y, const T& v)
33   {
34     while (x <= X) {
35       add_(x, y, v);
36       x += x & -x;
37     }
38   }
39 
40   void add_(int x, int y, const T& v)
41   {
42     while (y <= Y) {
43       tree[x][y] += v;
44       y += y & -y;
45     }
46   }
47 };
48 
49 int main()
50 {
51   int insn;
52   static BinaryIndexedTree2<int> bit;
53   int S;
54   while (scanf("%d", &insn) != EOF && insn != 3) {
55     switch (insn) {
56       case 0:
57         {
58           scanf("%d", &S);
59           bit.X = bit.Y = S;
60           for (int i = 0; i <= S; i++) {
61             fill_n(bit.tree[i], S+1, 0);
62           }
63         }
64         break;
65       case 1:
66         {
67           int X, Y, A;
68           scanf("%d %d %d", &X, &Y, &A);
69           bit.add(X+1, Y+1, A);
70         }
71         break;
72       case 2:
73         {
74           int L, B, R, T;
75           scanf("%d %d %d %d", &L, &B, &R, &T);
76           printf("%d\n", bit.read(R+1, T+1) - bit.read(L, T+1) - bit.read(R+1, B) + bit.read(L, B));
77         }
78         break;
79     }
80   }
81   return 0;
82 }