카테고리 없음

[백준] [C++] 11505번 구간 곱 구하기 (segment tree)

느스그 2021. 7. 10. 22:07

1. 문제

 

11505번: 구간 곱 구하기 (acmicpc.net)

 

11505번: 구간 곱 구하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄

www.acmicpc.net

 

2. 풀이

커피숍 문제와 똑같이 문제를 해결하였다.

 

 

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
 
using namespace std;
int N, M, K;
vector<long long> number;
vector<long long> seg;
const long long MOD = 1000000007;
 
long long init(int lo, int hi, int idx) {
    if(lo + 1 == hi) {
        return seg[idx] = number[lo];
    }
    int mid = (lo + hi) / 2;
    return seg[idx] = (init(lo, mid, idx*2) * init(mid, hi, idx*2 + 1)) % MOD;
}
 
long long update(int lo, int hi, int idx, int ni) {
    if(lo + 1 == hi) {
        return seg[idx] = number[ni];
    }
    int mid = (lo + hi)/2;
    if(ni < mid) {
        return seg[idx] = (update(lo, mid, idx*2, ni) * seg[idx*2 + 1])%MOD;
    }
    else {
        return seg[idx] = (update(mid, hi, idx*2 + 1, ni) * seg[idx*2])%MOD;
    }
}
long long product(int lo, int hi, int idx, int start, int end) {
    if(lo == start && hi == end) {
        return seg[idx];
    }
    int mid = (lo + hi) / 2;
    if(end <= mid) {
        return product(lo, mid, idx*2, start, end);
    }
    else if(mid <= start) {
        return product(mid, hi, idx*2 + 1, start, end);
    }
    else {
        return (product(lo, mid, idx*2, start, mid) * product(mid, hi, idx*2 + 1, mid, end))%MOD;
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>M>>K;
    number = vector<long long>(N);
    seg = vector<long long>(N*5);
    for(int i = 0; i < N; i++) {
        cin>>number[i];
    }
    init(0, N, 1);
    for(int i = 0; i < M + K; i++) {
        int a, b, c;
        cin>>a>>b>>c;
        if(a == 1) {
            number[b - 1] = c;
            update(0, N, 1, b - 1);
        }
        else {
            if(b > c) {
                swap(b, c);
            }
            cout<<(product(0, N, 1, b - 1, c)%MOD)<<"\n";
        }
    }
    
}
cs