[백준][C++] 11505: 구간 곱 구하기

문제 링크: https://www.acmicpc.net/problem/11505

 

구간 곱 세그먼트 트리를 만들면 됩니다.

query를 할 때 구간과 겹치지 않을때 항등원 1을 return 하는 점 참고해주세요. 그리고 모듈러 연산을 해야되니 이 점도 염두해야 합니다.

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MOD = 1000000007;



// 구간곱
vector<ll> tree;

// node -> 1
// [node_l, node_r] -> [0, n-1]
ll init(vector<ll>& arr, int node_l, int node_r, int node) {
	if (node_l == node_r) return tree[node] = arr[node_l];

	int mid = (node_l + node_r) / 2;
	return tree[node] = ((init(arr, node_l, mid, node * 2)%MOD) * (init(arr, mid + 1, node_r, node * 2 + 1)%MOD)) % MOD;
}

ll query(const int& l, const int& r, int node_l, int node_r, int node) {
	if (r < node_l || node_r < l) return 1;	// 구간과 겹치지 않는 경우
	if (l <= node_l && node_r <= r) return tree[node];	// node 표현범위가 arr[l, r]에 포함되는 경우

	int mid = (node_l + node_r) / 2;
	return ((query(l, r, node_l, mid, node * 2) % MOD) * (query(l, r, mid + 1, node_r, node * 2 + 1)%MOD)) % MOD;
}

ll update(const int& idx, const ll& newValue, int node_l, int node_r, int node) {
	if (idx < node_l || node_r < idx) return tree[node];	// 구간과 겹치지 않는 경우
	if (node_l == node_r) return tree[node] = newValue;		// leaf

	int mid = (node_l + node_r) / 2;
	return tree[node] = ((update(idx, newValue, node_l, mid, node * 2)%MOD) * (update(idx, newValue, mid + 1, node_r, node * 2 + 1)%MOD)) % MOD;
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n, m, k;
	cin >> n >> m >> k;

	vector<ll> arr(n);
	for (auto& c : arr)
		cin >> c;

	tree.resize(4 * n);
	init(arr, 0, n - 1, 1);

	while (m + k) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == 1) {
			update(b - 1, c, 0, n - 1, 1);
			--m;
		}
		else {
			cout << query(b - 1, c - 1, 0, n - 1, 1) << '\n';
			--k;
		}
	}

	return 0;
}