백준 13076번 [Distinct rational numbers](C++)-yes6686- 티스토리

백준 문제 풀이: 13076 [Distinct rational numbers]

---

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

문제 설명:

주어진 정수 배열에 대해 다음과 같은 연산을 효율적으로 수행하는 문제입니다:

• 1 x y: 배열의 x번째 값을 y로 변경
• 2 x y: 배열의 x번째 값부터 y번째 값까지의 곱을 구한 후, 해당 값을 1,000,000,007로 나눈 나머지를 출력

여기서 효율적인 계산을 위해 세그먼트 트리를 사용합니다. 세그먼트 트리는 구간 곱을 빠르게 계산할 수 있으며, 값을 업데이트하는 데도 유용합니다.

또한, 모듈러 연산을 통해 큰 정수 값이 발생하는 것을 방지합니다. 이를 통해 오버플로우를 방지하고 계산을 최적화합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

long long int arr[1000001];
long long int seg[4000001];

long long int go(int n, int s, int e) {
    if (s == e) {
        return seg[n] = arr[s];
    } else {
        int mid = (s + e) / 2;
        long long int left = go(2 * n, s, mid);
        long long int right = go(2 * n + 1, mid + 1, e);
        seg[n] = (left * right) % 1000000007;
        return seg[n];
    }
}

long long int mul(int n, int s, int e, int l, int r) {
    if (e < l || r < s) return 1;
    if (l <= s && r >= e) {
        return seg[n];
    }
    int mid = (s + e) / 2;
    long long int left = mul(n * 2, s, mid, l, r);
    long long int right = mul(n * 2 + 1, mid + 1, e, l, r);
    return (left * right) % 1000000007;
}

int change(int n, int s, int e, int i, long long int d) {
    if (i < s || i > e) return seg[n];
    if (s == e) {
        seg[n] = d;
        return seg[n] % 1000000007;
    }
    if (s != e) {
        int mid = (s + e) / 2;
        long long int left = change(n * 2, s, mid, i, d);
        long long int right = change(n * 2 + 1, mid + 1, e, i, d);
        return seg[n] = (left * right) % 1000000007;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    go(1, 0, n - 1);
    long long int a, b, c;
    for (int i = 0; i < m + k; i++) {
        cin >> a >> b >> c;
        if (a == 1) {
            arr[b - 1] = c;
            change(1, 0, n - 1, b - 1, c);
        } else if (a == 2) {
            cout << mul(1, 0, n - 1, b - 1, c - 1) % 1000000007 << '\n';
        }
    }
}

---

코드 설명

• 세그먼트 트리 구현:
  • go: 세그먼트 트리를 초기화합니다. 배열의 구간 곱을 저장합니다.
  • mul: 특정 구간의 곱을 계산하여 반환합니다.
  • change: 배열의 특정 값을 변경하고 세그먼트 트리를 업데이트합니다.
• 모듈러 연산: 큰 수를 처리하기 위해 모든 곱셈 연산에 대해 모듈러 연산을 수행합니다. 이 작업은 결과 값이 1,000,000,007 이하가 되도록 보장합니다.
• 시간 복잡도: O((n + m + k) log n)
  • 세그먼트 트리 초기화: O(n log n)
  • 각 연산 (구간 곱 및 업데이트): O(log n)

---

결과

주어진 배열에 대해 효율적으로 구간 곱 및 값을 업데이트할 수 있습니다. 세그먼트 트리와 모듈러 연산의 조합을 통해 높은 효율성을 제공합니다. 추가적인 최적화 방법이나 질문이 있다면 댓글로 공유 부탁드립니다!