BOJ 15646 - 농부 후안은 바리스타입니다

BOJ 15646 - 농부 후안은 바리스타입니다

2차원 펜윅 트리를 이용해 쉽게 풀 수 있다.

iMOS 법을 써서 네 점만 업데이트 하면, 구간 합 쿼리를 이용하면 특정 점의 현재 값을 알 수 있다.

struct fenwick2d {  
   int Y, X;  
   vector<vector<ll>> tree;  
   fenwick2d(int Y, int X) : Y(Y), X(X) {  
      tree = vector<vector<ll>>(Y + 2, vector<ll>(X + 2));  
   }  
  
   void _update(int y, int _x, ll d) {  
      while (y <= Y) {  
         int x = _x;  
         while (x <= X) {  
            tree[y][x] += d;  
            x += x & -x;  
         }  
         y += y & -y;  
      }  
   }  
  
   void update(int y1, int x1, int y2, int x2, ll d) {  
      _update(y1, x1, d);  
      _update(y2 + 1, x2 + 1, d);  
      _update(y1, x2 + 1, -d);  
      _update(y2 + 1, x1, -d);  
   }  
  
   ll query(int y, int _x) {  
      ll ret = 0;  
      while (y) {  
         int x = _x;  
         while (x) {  
            ret += tree[y][x];  
            x -= x & -x;  
         }  
         y -= y & -y;  
      }  
      return ret;  
   }  
};  
  
void solve() {  
   int Y, X, Q;  
   cin >> X >> Y >> Q;  
   fenwick2d fenw(Y, X);  
   while (Q--) {  
      int c, x1, y1, x2, y2, d;  
      cin >> c;  
      if (c == 1) {  
         cin >> x1 >> y1 >> x2 >> y2 >> d;  
         fenw.update(y1, x1, y2, x2, d);  
      } else {  
         cin >> x1 >> y1;  
         cout << fenw.query(y1, x1) << endl;  
      }  
   }  
}