링크 : https://www.acmicpc.net/problem/11505
이 문제 또한 세그먼트 트리로 구하면 되는 문제 입니다.
주의할 점은, MOD할 때 질의부분과 업데이트 부분, 그리고 init 부분 모두 해줘야 한다는 점이며, 범위가 아닌 부분을 MUL할 때 0을 반환하면 안되고, 1을 반환해 주어야 한다는 점 입니다.
소스코드 :
이 문제 또한 세그먼트 트리로 구하면 되는 문제 입니다.
주의할 점은, MOD할 때 질의부분과 업데이트 부분, 그리고 init 부분 모두 해줘야 한다는 점이며, 범위가 아닌 부분을 MUL할 때 0을 반환하면 안되고, 1을 반환해 주어야 한다는 점 입니다.
소스코드 :
| 
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 
73 
74 
75 
76 | 
#include <iostream> 
#include <vector> 
#include <list> 
#include <string> 
#include <queue> 
typedef long long ll; 
using namespace std; 
int n, m, k; 
ll MOD = 1000000007; 
ll num[1000001]{ 1, }; 
ll tree[1000001 * 4]{ 1, }; 
ll Init(int node, int start, int end) { 
    if (start == end) { 
        return tree[node] = num[start]; 
    } 
    int mid = (start + end) / 2; 
    return tree[node] = (Init(2 * node, start, mid) * Init(2 * node + 1, mid + 1, end)) % MOD; 
} 
ll update(int index, int newValue, int node, int start, int end) { 
    if (index < start || end < index) { 
        return tree[node]; 
    } 
    if (start == end) 
        return tree[node] = newValue; 
    int mid = (start + end) / 2; 
    return tree[node] = (update(index, newValue, node * 2, start, mid) * update(index, newValue, node * 2 + 1, mid + 1, end)) % MOD; 
} 
ll Sum(int left, int right, int node, int start, int end) { 
    if (left <= start && end <= right) { 
        return tree[node]; 
    } 
    if (right < start || end < left) { 
        return 1; 
    } 
    int mid = (start + end) / 2; 
    return (Sum(left, right, node * 2, start, mid) * Sum(left, right, node * 2 + 1, mid + 1, end)) % MOD; 
} 
int main() { 
    cin.tie(0); 
    ios_base::sync_with_stdio(false); 
    cin >> n >> m >> k; 
    for (int i = 1; i <= n; i++) { 
        cin >> num[i]; 
    } 
    // Initiating of seg tree. 
    Init(1, 1, n); 
    for (int i = 1; i <= m + k; i++) { 
        int a, b, c; 
        cin >> a >> b >> c; 
        if (a == 1) { 
            update(b, c, 1, 1, n); 
        } 
        else { 
            cout << Sum(b, c, 1, 1, n) << '\n'; 
        } 
    } 
} | cs | 
댓글
댓글 쓰기