白駿11505区間乗

質問リンク

質問する

キー(Key)

試行錯誤

コード#コード#

#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';
		}
	}


}

ポスト