백준 11505 구간곱

문제링크

https://www.acmicpc.net/problem/11505

문제

키포인트

기본적인 세그먼트 트리 응용 문제이다.
다만 구간 덧셈 문제는 원래값과 갱신값 차이를 이용해 부모 노드부터 내려가면서 값을 즉시 갱신해줄 수 있었지만 이 문제는 업데이트시 리프노드부터 시작해 가지 전체를 갱신해 주어야 한다.
덧셈에 대한 세그먼트 트리만 알고 풀었는데 생각보다 고전했다.

시행착오

init 함수에서 나머지 연산을 실행 한 init반환값끼리 곱한 후 한번더 나머지 연산을 해주어야 했는데 간과해서 출력초과가 엄청났다. (바보)

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
int n, m, k;
ll init(vector<ll> &a, vector<ll> &tree, int node, int start, int end) {
	if (start == end) {
		return tree[node] = a[start];
	}
	else {
		return tree[node] = (init(a, tree, node * 2, start, (start + end) / 2) * init(a, tree, node * 2 + 1, (start + end) / 2 + 1, end)) % MOD;
	}
}
ll mul(vector<ll> &tree, 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];
	}
	return (mul(tree, node * 2, start, (start + end) / 2, left, right)* mul(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right)) % MOD;
}
ll update(vector<ll> &tree, int node, int start, int end, int index, ll newVal) {
	if (index < start || index > end) return tree[node];
	if (start != end) {
		return tree[node] = ((update(tree, node * 2, start, (start + end) / 2, index, newVal) % MOD)
			*(update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, newVal) % MOD)) % MOD;

	}
	else if (start == index) return tree[node] = newVal % MOD;
	else return tree[node];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k;
	int h = (int)ceil(log2(n));
	int tree_size = (1 << (h + 1));

	vector<ll> a(n + 1);
	vector<ll> tree(tree_size + 1);


	for (int i = 1; i <= n; i++) cin >> a[i];
	init(a, tree, 1, 1, n);

	for (int i = 0; i < m + k; i++) {
		ll aa, bb, cc;
		cin >> aa >> bb >> cc;
		if (aa == 1) {
			update(tree, 1, 1, n, bb, cc);
			a[bb] = cc;
		}
		else if (aa == 2) {
			cout << mul(tree, 1, 1, n, bb, cc) << '\n';
		}
	}


}

후기

기본적으로 세그먼트 트리 알고리즘을 알고있다면 조금만 생각하면 쉽게 해결할 수 있는 문제이기는하다.
다음에 다시한번 풀어보자.