-
Notifications
You must be signed in to change notification settings - Fork 1
/
11505.cpp
91 lines (78 loc) · 2.01 KB
/
11505.cpp
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <vector>
#include <cmath>
#define MOD 1000000007
using namespace std;
template <typename T>
class SegmentTree {
private:
vector<T> tree;
vector<T> a;
int n;
T (*func)(T, T);
void init(int node, int start, int end) {
if (start == end) {
tree[node] = a[start];
} else {
init(node*2, start, (start+end)/2);
init(node*2+1, (start+end)/2+1, end);
tree[node] = func(tree[node*2], tree[node*2+1]);
}
}
T query(int node, int start, int end, int left, int right) {
if (left > end || right < start) return 1;
if (left <= start && end <= right) return tree[node];
T lval = query(node*2, start, (start+end)/2, left, right);
T rval = query(node*2+1, (start+end)/2+1, end, left, right);
return func(lval, rval);
}
void update(int node, int start, int end, int index, T val) {
if (index < start || index > end) return;
if (start == end) {
a[index] = val;
tree[node] = val;
return;
}
update(node*2, start, (start+end)/2, index, val);
update(node*2+1, (start+end)/2+1, end, index, val);
tree[node] = func(tree[node*2], tree[node*2+1]);
}
public:
SegmentTree(vector<T> &arr, T (*f)(T, T)) : a(arr), func(f) {
n = arr.size();
int h = (int)ceil(log2(n));
int tree_size = (1 << (h+1));
tree.resize(tree_size);
init(1, 0, n-1);
}
T query(int left, int right) {
return query(1, 0, n-1, left, right);
}
void update(int index, T val) {
update(1, 0, n-1, index, val);
}
};
long long multiply(long long a, long long b) {
return a * b % MOD;
}
void solve(void) {
int n, m, k;
cin >> n >> m >> k;
vector<long long> a(n);
for (int i=0; i<n; i++) {
cin >> a[i];
}
SegmentTree<long long> st(a, multiply);
for (int i=0; i<m+k; i++) {
int a, b, c;
cin >> a >> b >> c;
if (a == 1) st.update(b-1, c);
else cout << st.query(b-1, c-1) << "\n";
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
solve();
return 0;
}