BOJ 1275: 커피솝 2

작성일

https://www.acmicpc.net/problem/1275

  • 3월동안 210문제 풀기 (7/210)
  • 간단한 구간 트리 문제. 펜윅 트리로 풀어봄
  • long long 때문에 겁나게 틀림
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;

typedef long long IType;
class Fenwick {
  int N, maxSegment = 1;
  vector<IType> tree;
public:
  Fenwick(int n): N(n), tree(n+1) {
    while(maxSegment < n) maxSegment *= 2;
    maxSegment /= 2;
  }
  void update(int p, IType val) {
    for(int i = p; i <= N; i += i & -i)
      tree[i] += val;
  }
  IType query(int p) {
    IType res = 0;
    for(int i = p; i > 0; i -= i & -i)
      res += tree[i];
    return res;
  }
  int findBound(IType target) {
    int pos = 0;
    for(int segSize = maxSegment; segSize > 0; segSize /= 2)
      if(tree[pos + segSize] < target)
        pos += segSize, target -= tree[pos];
    return pos;
  }
};


int main() {
  int N, Q, x, y, a, b;
  scanf("%d %d", &N, &Q);
  vector<IType> arr(N+1);
  Fenwick fwt(N);
  for(int i = 1; i <= N; i++) {
    scanf("%lld", &arr[i]);
    fwt.update(i, arr[i]);
  }
  for(int i = 0; i < Q; i++) {
    scanf("%d %d %d %d", &x, &y, &a, &b);
    if(x > y) swap(x,y);
    printf("%lld\n", fwt.query(y) - fwt.query(x-1));
    fwt.update(a,b-arr[a]);
    arr[a] = b;
  }
}