[BOJ] #11505 구간 곱 구하기

시간 제한	메모리 제한	정답 비율
1 초	256 MB	33.686 %

11505번: 구간 곱 구하기

 

문제

 

해결

key point, 세그먼트 트리, '최솟값'과 방식 동일

2021/02/15 - [🔥 PS(Problem Solving) 🔥/BOJ] - [BOJ] #10868 최솟값

• 위에 보이는 최솟값 문제와 방법은 동일하나 구간의 곱을 구해야 하는 문제이다.
• 따라서, 초기화를 따로 해줄 필요가 없고,
• update 함수에서 seg[i]값을 저장할 때, 구간의 곱을 저장해야 하며
• query함수에서 구간의 곱을 리턴해야 한다.

 

코드

메모리	시간
17616 KB	324 ms

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define mod 1000000007
vector<long long int>seg;
int n, m, k;
int h = 1;
void update(int i, int val) {
    i += h - 1;
    seg[i] = val;
    while (i > 1) {
        i /= 2;
        seg[i] = (seg[i * 2] * seg[i * 2 + 1]) % mod;
    }
}
long long int query(int l, int r, int num, int nl, int nr) {
    //l,r이 찾으려는 범위, num이 현재 보고 있는 노드
    //nl,nr 현재 보고있는 범위
    if (l <= nl && nr <= r) return seg[num];
    else if (nl > r || nr < l) return 1;
    int mid = (nl + nr) / 2;
    return (query(l, r, num * 2, nl, mid) * query(l, r, num * 2 + 1, mid + 1, nr)) % mod;
}
int main() {
    scanf("%d %d %d", &n, &m, &k);
    while (h < n) h <<= 1; //높이구하기 1 2 4 8
    seg.resize(h * 2);
    for (int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num);
        update(i + 1, num);
    }
    for (int i = 0, a, b, c; i < m + k; i++) {
        scanf("%d %d %d", &a, &b, &c);
        if (a == 1) update(b, c);
        else printf("%lld\n", query(b, c, 1, 1, h));
    }
    return 0;
}