백준 11505번 구간 곱 구하기 - C++(cpp) 풀이

---

 

1. 펜윅트리를 이용해서 업데이트와 누적곱을 연산을 구현한다.
2. 또 다른 펜윅트리를 이용해서 대상 구간 내에 0이 있는지 체크한다.

 

1. 펜윅트리를 이용해서 업데이트와 누적곱을 연산을 구현한다.

 계속 변화하는 수열에서 구간곱을 구해야한다. 세그먼트트리 또는 펜윅트리를 사용한다. 아래 코드에서는 펜윅트리를 사용하였다. 구간곱 펜윅트리 구현은 아래와 같이 하였다.

1. 초기 트리 배열의 값을 0이 아닌 1로 초기화한다.
2. 나눗셈은 페르마의 소정리를 이용해 역원을 곱해주는 것으로 처리한다.

 b번째 수를 c로 업데이트 하는 연산은, 원래 값이 x라고 하면 b번째 수를 x로 나눈 뒤, 다시 c를 곱해주는 연산을 해주면 된다. 이때 x로 나누는 연산을 x의 모듈러 역원을 곱해주는 것으로 처리해준다. 어차피 출력해야 하는 것은 1,000,000,007로 나눈 나머지이기 때문에 페르마의 소정리를 이용하였다.

 b번째 수부터 c번째 수까지의 구간곱은, b번째 수까지의 누적곱 ÷ (c-1)번째 수까지의 누적곱이 된다. 이때도 나눗셈은 역원을 곱해주는 것으로 처리하면 된다.

 

2. 또 다른 펜윅트리를 이용해서 대상 구간 내에 0이 있는지 체크한다.

 까다로운 점은 어떤 수가 0이 될 수도 있다는 것이다. 어떤 수를 펜윅트리내에서 0으로 만들어버리면 뭘 곱해도 0에서 변하지 않기 때문에 더 이상 업데이트 연산이 불가능하다. 따라서 0은 실제로 업데이트해주지 않고 해당 수가 0임을 또 다른 펜윅트리(구간합 용)에 기록해준다.

 이후 구간곱 쿼리가 들어오면 0 여부를 기록해둔 펜윅트리(구간합)에서 대상 구간내의 0의 개수를 구해 0이 있다면 바로 0을 출력해준다. 어떤 수가 0에서 0이 아닌 수로 업데이트되었다면 다시 0 여부를 기록하는 펜윅트리(구간합)에 이 사실을 업데이트해준다.

 맨 처음 초기 상태에서도 0이 들어올 수 있다는 점을 주의해야 한다. 초기 수열을 입력받을 때 0이 들어오면 펜윅트리(구간곱)에 업데이트 연산을 해주지 않고 0을 기록하는 펜윅트리(구간합)에 0 개수를 업데이트해주고, 초기 수열의 값을 1로 처리해주어야 한다.

 

반응형

---

#include <iostream>
#include <vector>

using namespace std;

int MOD = 1000000007;
int N, M, K;
int arr[1000001];
vector<long long> tree(1000001, 1);
vector<int> zero_tree(1000001);

long long pow(int x, int n) {
    if (n == 1) return x;
    
    long long half = pow(x, n/2);
    
    if (n % 2 == 0) return half * half % MOD;
    else return (half * half % MOD) * x % MOD;
}

long long moduloInverse(int x) {
    return pow(x, MOD-2);
}

long long pmul(int pos) {
    if (pos == 0) return 1;
    
    long long ret = 1;
    
    while (pos > 0) {
        ret = ret * tree[pos] % MOD;
        pos &= (pos - 1);
    }
    
    return ret;
}

void multiply(int pos, int val) {
    while (pos < tree.size()) {
        tree[pos] = tree[pos] * val % MOD;
        pos += (pos & -pos);
    }
}

int psum(int pos) {
    if (pos == 0) return 0;
    
    int ret = 0; 
    
    while (pos > 0) {
        ret += zero_tree[pos];
        pos &= (pos - 1);
    }
    
    return ret;
}

void add(int pos, int val) {
    while (pos < zero_tree.size()) {
        zero_tree[pos] += val;
        pos += (pos & -pos);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M >> K;

    for(int i=1; i<=N; i++) {
        cin >> arr[i];
        
        if (arr[i] == 0) {
            add(i, 1);
            arr[i] = 1;
        }
        else {
            multiply(i, arr[i]);
        }
    }
    
    int a, b, c;
    
    for(int i=0; i<M+K; i++) {
        cin >> a >> b >> c;
        
        if (a == 1) {
            if (c == 0) {
                add(b, 1);
            }
            else {
                if (psum(b) - psum(b-1) > 0) add(b, -1);
                multiply(b, moduloInverse(arr[b]));
                multiply(b, c);
                arr[b] = c; 
            }
        }
        else {
            if (psum(c) - psum(b-1) > 0) cout << 0 << "\n";
            else cout << pmul(c) * moduloInverse(pmul(b-1)) % MOD << "\n";
        }
    }

    return 0;
}