티스토리 뷰

알고리즘 관련/BOJ

BOJ)11505 구간 곱 구하기

JASON 자손9319 2017. 1. 12. 23:43

문제:icpc.me/11505


구간에 대한 곱을 출력하는 문제이다. 값의 갱신이 빈번하게 일어나기 때문에 세그먼트 트리를 이용해주면 된다.


곱셈의 특성상 구간의 곱을 가지고 있으면 무수히 커질 수 있기 때문에 문제에서 모듈러연산을 요구한다.


이때 단순히 답에만 모듈러연산을 해준다면 노드가 가지고 있는 값이 오버플로우 될 수 있으므로 우리는 노드가 가진 값들을 업데이트 할 때 와 쿼리를 처리할 때도 모듈러연산을 해줘야 한다.


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
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MOD 1000000007
#define MAX_N 1000000
typedef long long ll;
using namespace std;
ll n, m, k, t, x, y, z;
ll seg[4*MAX_N];
ll update(ll pos, ll val, ll node, ll x, ll y){
    if (y < pos || pos < x)
        return seg[node];
    if (x == y)
        return seg[node] = val;
    ll mid = (x + y) >> 1;
    return seg[node] = (update(pos, val, node * 2, x, mid)*update(pos, val, node * + 1, mid + 1, y)) % MOD;
}
ll query(ll lo, ll hi, ll node, ll x, ll y){
    if (y < lo || hi < x)
        return 1;
    if (lo <= x&&<= hi)
        return seg[node];
    ll mid = (x + y) >> 1;
    return (query(lo, hi, node * 2, x, mid)*query(lo, hi, node * + 1, mid + 1, y)) % MOD;
}
int main(){
    scanf("%lld%lld%lld"&n, &m, &k);
    for (ll i = 1; i <= n; i++){
        scanf("%lld"&t);
        update(i, t, 11, n);
    }
    for (ll i = 0; i < m + k; i++){
        scanf("%lld%lld%lld"&x, &y, &z);
        if (x == 1)
            update(y, z, 11, n);
        else
            printf("%lld\n", query(y, z, 11, n));
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1395 스위치  (0) 2017.01.13
BOJ)10999 구간 합 구하기2  (1) 2017.01.13
BOJ)11505 구간 곱 구하기  (2) 2017.01.12
BOJ)5012 불만 정렬  (2) 2017.01.11
BOJ)3002 아날로그 다이얼  (0) 2017.01.11
BOJ)1168 조세퍼스 문제2  (0) 2017.01.11
댓글
댓글쓰기 폼