-
Notifications
You must be signed in to change notification settings - Fork 0
/
11505BOJ_interval_mul.cpp
54 lines (46 loc) · 1.15 KB
/
11505BOJ_interval_mul.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
#include <iostream>
#include <vector>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
using ll = unsigned long long;
const ll D = 1000000007;
int n,m,k;
struct SegTree
{
vector<ll> tree;
void init(int n, vector<ll> &arr){
tree.resize(2*n);
for (int i=0; i<n; ++i) tree[i+n] = arr[i];
for (int i=n-1; i>0; --i) tree[i] = tree[i<<1] * tree[i<<1|1] % D;
}
void update(int x, ll z){
x += n-1;
tree[x] = z;
while (x >> 1){
tree[x>>1] = tree[x] * tree[x^1] % D;
x>>=1;
}
}
ll query(int l, int r){
ll ret = 1;
for (l+=n-1, r+=n; l<r; l>>=1, r>>=1){
if (l&1) ret = ret * tree[l++] % D;
if (r&1) ret = ret * tree[--r] % D;
}
return ret;
}
} tree;
int main()
{
fastio
cin >> n >> m >> k;
vector<ll> arr(n);
for (int i=0; i<n; ++i) cin >> arr[i];
tree.init(n, arr);
int T = m+k;
while (T--){
int x, l, r; cin >> x >> l >> r;
if (x == 1) tree.update(l, r);
else cout << tree.query(l,r) <<'\n';
}
} // namespace std;