[백준] 구간 곱 구하기

[hye-on]

🔗 구간 곱 구하기

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

```cpp #include #include using namespace std; int N, M, K; typedef long long ll; //세그먼트 트리 - 구현 기억 안남 vectorv; vectortree; int MOD = 1000000007; ll init(int start, int end, int node) { //v의 시작 ~끝, node: tree의 노드를 가르킴 if (start == end) return tree[node] = v[start]; int mid = (start + end) / 2; //재귀적으로 두 구간으로 나누고 그 곱을 나로 함 return tree[node] = (init(start, mid, node * 2) * init(mid+1, end, node * 2 + 1))% MOD; // {0, 10, 1} -> {0, 5, 2} + {6,10,3} } void update(int start, int end, int node, int idx, int dif, int dif2) { // double로 하면 손실 값 생길것 같다. //범위 밖 if (idx < start || end < idx) return; if (start == end) { tree[node] = dif2; v[idx] = dif2; return; } //내려가면서 계속 갱신 int mid = (start + end) / 2; update(start, mid, node * 2, idx, dif, dif2); update(mid + 1, end, node * 2 + 1, idx, dif, dif2); tree[node] = ((tree[node * 2] % MOD )* (tree[node * 2 + 1] % MOD)) % MOD; } //구간 곱 구하기 ll multi(int start, int end, int node, int left, int right) { //범위 안에 없음 if (right < start || end < left) return 1; //범위 안 if (left <= start && end <= right) return tree[node]; //범위 걸치면 int mid = (start + end) / 2; return (multi(start, mid, node * 2, left, right))% MOD * (multi(mid + 1, end, node * 2 + 1, left, right)%MOD)% MOD; } int main() { cin >> N >> M >> K; v.resize(N + 1); tree.resize(4 * N); // (N보다 조금 큰 값 (제곱수) )*2< N * 4 for (int i = 0; i < N; i++) cin >> v[i]; int cmd = 0, b = 0, c = 0; init(0, N - 1, 1); for (int i = 0; i < M + K; i++) { cin >> cmd >> b >> c; if (cmd == 1) { update(0, N - 1, 1, b - 1, v[b - 1], c); } else cout << multi(0, N - 1, 1, b - 1, c - 1) << "\n"; } } ```

코멘트

- 세그먼트 트리 문제였는데 덧셈하고 좀 다른 부분이 까다로웠던 것 같습니다.

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java import java.io.*; import java.util.*; /** * 22:05 시작! */ public class Main { /** * 누적합? */ static int MOD = 1_000_000_007; static long[] nums, tree; public static void main(String[] args) throws Exception { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(bf.readLine()); StringBuilder answer = new StringBuilder(); int n = Integer.parseInt(st.nextToken()); // 최대 100만 int m = Integer.parseInt(st.nextToken()); // 최대 1만 int k = Integer.parseInt(st.nextToken()); // 최대 1만 nums = new long[n + 1]; for(int i = 1; i <= n; ++i) { nums[i] = Integer.parseInt(bf.readLine()); } tree = new long[n * 4]; initTree(1, n, 1); for(int i = 0; i < m + k; ++i) { st = new StringTokenizer(bf.readLine()); int cmd = Integer.parseInt(st.nextToken()); int arg1 = Integer.parseInt(st.nextToken()); int arg2 = Integer.parseInt(st.nextToken()); if(cmd == 1) { update(1, n, 1, arg1, arg2); continue; } // cmd == 2 answer.append(multiply(1, n, 1, arg1, arg2) % MOD) .append("\n"); } System.out.println(answer.toString()); } static long initTree(int start, int end, int node) { if(start == end) return tree[node] = nums[start]; int mid = (start + end) / 2; return tree[node] = (initTree(start, mid, node * 2) * initTree(mid + 1, end, node * 2 + 1)) % MOD; } static long update(int start, int end, int node, int idx, int value) { if(end < idx || idx < start) return tree[node]; if(start == end) return tree[node] = value; int mid = (start + end) / 2; return tree[node] = (update(start, mid, node * 2, idx, value) * update(mid + 1, end, node * 2 + 1, idx, value)) % MOD; } static long multiply(int start, int end, int node, int left, int right) { if(end < left || right < start) return 1; if(left <= start && end <= right) return tree[node]; int mid = (start + end) / 2; return (multiply(start, mid, node * 2, left, right)* multiply(mid + 1, end, node * 2 + 1, left, right)) % MOD; } } ```

코멘트

-