BOJ 11505: 구간 곱 구하기

작성일

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

  • 2월동안 187문제 풀기(지난달 누적 87개) (63/187)
  • 세그먼트 트리, 리뷰용 문제(https://codeforces.com/blog/entry/18051)
  • 완벽한 바이너리 Tree가 만들어진다.
    • 업데이트 시에는 해당 위치의 모든 부모들(절반의 절반들)을 모두 업데이트 한다.
    • 쿼리 시에는 왼쪽과 오른쪽 위치에서 계속 좁혀오되, 왼쪽에서는 홀수번, 오른쪽에서는 짝수번 트리를 찾는다.
    • 왼쪽 기준 홀수면(예를들어 5->2) 나눠졌을때 5를 루트로 하는 트리가 범위에서 벗어나게 된다.
    • 오른쪽 기준 짝수면(예를들어 12->6) 12가 6이 되었을때 범위가 더 늘어나버린다. (6은 12,13을 포함) 그러므로 12는 계산해 버리고 1을 뺀 뒤 나눠서 5로 만든다.
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
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
struct SegmentTree {
  int N;
  vector<LL> t;

  LL INIT = 1;
  LL MOD = 1e9+7;
  inline LL f(LL a, LL b) {
    return (a * b)%MOD;
  }

  SegmentTree(int n) : N(n), t(2*n) {
    for(int i = N; i < 2*N; i++)
      scanf("%lld", &t[i]);
    build();
  }

  void build() {
    for (int i = N-1; i > 0; i--)
      t[i] = f(t[2*i], t[2*i+1]);
  }

  void update(int p, int v) {
    for (t[p += N] = v; p > 1; p /= 2)
      t[p/2] = f(t[p], t[p^1]);
  }

  LL query(int l, int r) {
    LL res = INIT;
    for(l += N, r += N; l < r; l /= 2, r /= 2) {
      if(l&1) res = f(res, t[l++]);
      if(r&1) res = f(res, t[--r]);
    }
    return res;
  }
};

int main() {
  int N, M, K, a,b,c;
  scanf("%d %d %d", &N, &M, &K);
  SegmentTree seg(N);
  for(int i = 0; i < M+K; i++) {
    scanf("%d %d %d", &a, &b, &c);
    if(a == 1) seg.update(b-1, c);
    if(a == 2) {
      LL res = seg.query(b-1,c);
      printf("%lld\n", res);
    }
  }
  return 0;
}