https://www.acmicpc.net/problem/11505
11505번: 구간 곱 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 회수이고, K는 구간의 곱을 구하는 회수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+2번째 줄까지 세 개의 정수 a,b,c가 주어지는데, a가 1인 경우 b번째 수를 c (0 ≤ c ≤ 1,000,000)로 바꾸고 a가 2인 경우에
www.acmicpc.net
ll query(int now, int left, int right, int start, int end) {
if (left > end || right < start) return 1;
if (left <= start && end <= right) return tree[now];
int mid = (start + end) / 2;
return (query(now * 2, left, right, start, mid) * query(now * 2 + 1, left, right, mid + 1, end)) % DIV;
}범위에서 벗어낫을때 return 1 을 해주는것이 이문제의 핵심이고, 알면 바로 풀 수 있다.
xor, + , *, -, & 연산 등등 문제에서 요구하는 연산이 무엇인지 잘 파악하고 함수를 짜야한다.
#include <iostream>
using namespace std;
#define MAX_N 1000001
#define DIV 1000000007
typedef long long ll;
ll tree[MAX_N * 4];
ll update_tree(int now, int target, int start, int end, int value) {
if (target > end || target < start) return tree[now];
if (start == end) return tree[now] = value;
int mid = (start + end) / 2;
return tree[now] = (update_tree(now * 2, target, start, mid, value) * update_tree(now * 2 + 1, target, mid + 1, end, value)) % DIV;
}
ll query(int now, int left, int right, int start, int end) {
if (left > end || right < start) return 1;
if (left <= start && end <= right) return tree[now];
int mid = (start + end) / 2;
return (query(now * 2, left, right, start, mid) * query(now * 2 + 1, left, right, mid + 1, end)) % DIV;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, M, K;
cin >> N >> M >> K;
for (int i = 0; i < N; i++) {
int data; cin >> data;
update_tree(1, i, 0, N - 1, data);
}
for (int i = 0; i < M + K; i++) {
int a, b, c;
cin >> a >> b >> c;
if (a == 1) {
update_tree(1, b - 1, 0, N - 1, c);
}
else {
cout << query(1, b - 1, c - 1, 0, N - 1) << "\n";
}
}
}