백준
백준 소스코드 [C++] 11505 구간 곱 구하기
Hani_Levenshtein
2020. 11. 10. 14:03
11505번: 구간 곱 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
백준 소스코드 [C++] 11505 구간 곱 구하기
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
typedef long long ll;
using namespace std;
#define mod 1000000007
int n, m, k;
vector<ll> tree,arr;
void input() {
cin >> n >> m >> k;
arr.resize(n);
tree.resize(4 * n);
for (int i = 0;i < n;i++) cin >> arr[i];
}
ll init(int i,int S,int E) {
if (S == E) return tree[i] = arr[S];
else return tree[i] = (init( 2 * i, S, (S + E) / 2) %mod)
* (init(2 * i + 1, (S + E) / 2 + 1, E) % mod) % mod;
}
ll update(int i, int S, int E, int idx,ll mul) {
if (idx < S || E < idx) return tree[i];
if (S == E) return tree[i] = mul;
return tree[i]=(update(2 * i, S, (S + E) / 2, idx,mul)%mod)
*(update(2 * i + 1, (S + E) / 2 + 1, E, idx,mul)%mod)%mod;
}
ll query( int i, int S, int E, int L, int R) {
if (E < L || R < S) return 1;
if (L <= S && E <= R) return tree[i];
return (query(2 * i, S, (S + E) / 2, L, R) % mod)
* (query(2 * i + 1, (S + E) / 2 + 1, E, L, R) % mod) % mod;
}
void output() {
int a, b, c;
for (int i = 0;i < m + k;i++) {
cin >> a >> b >> c;
if (a == 1) update(1, 0, n - 1, b - 1,c);
else cout<<query(1, 0, n - 1, b-1 , c-1)<<'\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
input();
init(1,0,n-1);
output();
return 0;
}