[백준 11505] 구간 곱 구하기 (C++)

11505번: 구간 곱 구하기

세그먼트 트리

---

구간의 곱을 구하는 문제라서 0을 신경써줘야 한다.

 

구간 합을 update할 때는 update값이 마이너스로 들어와서 부모부터 갱신이 가능했다. 하지만 곱을 update할 때는 안된다.

예를 들어서 3번째 수를 6으로 바꾸려고 하고 현재 3번째 수가 0인 경우를 생각해보자

 

구간 합을 구할 때와 조금 다르게 리프노드부터 업데이트해 나가면 편하다

3번째 수에 도달하면 (항상 리프노드일 것임) 6으로 업데이트 해주고, 구간 곱 트리를 처음에 만들어 줄 때와 비슷하게 node*2번 값과 node*2+1 번 값을 곱하면서 최상단 노드로 돌아온다.

리프노드부터 업데이트 해준다면 나누기를 해서 0인경우를 복잡하게 생각하지 않아도 된다.

 

 

답을 출력 할 때마다 '\n' 를 안해서 4번이나 틀렸다 개뭉충;

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<ll, ll>
#define MAX 1000001
typedef long long ll;
// typedef pair<ll, ll> pii;
 
using namespace std;
 
ll N, M, K;
ll arr[MAX];
ll tree[MAX * 4];
const ll MOD = 1000000007;
 
void input(){
    cin >> N >> M >> K;
    ll a, b, c;
    for(int i = 1; i <= N; i++){
        cin >> arr[i];
    }
}
 
ll make_tree(int startidx, int endidx, int node){
    if(startidx == endidx) return tree[node] = arr[startidx];
    int mid = (startidx + endidx) / 2;
    return tree[node] = (make_tree(startidx, mid, node*2) * \
                         make_tree(mid+1, endidx, node*2+1)) % MOD;
}
 
ll update_tree(int startidx, int endidx, int targetidx, ll update, int node){
    if(targetidx < startidx || targetidx > endidx) return tree[node];
    if(startidx == endidx) return tree[node] = update;
    
    int mid = (startidx + endidx) / 2;
    return tree[node] = (update_tree(startidx, mid, targetidx, update, node*2) *\
                         update_tree(mid+1, endidx, targetidx, update, node*2+1)) % MOD;
}
 
ll getQuery(int startidx, int endidx, int targetlidx, int targetridx, int node){
    if(targetridx < startidx || targetlidx > endidx) return 1;
    if(targetlidx <= startidx && endidx <= targetridx) return tree[node];
    int mid = (startidx + endidx) / 2;
    return (getQuery(startidx, mid, targetlidx, targetridx, node*2) * \
            getQuery(mid+1, endidx, targetlidx, targetridx, node*2+1)) % MOD;
}
 
void solve(){
    make_tree(1, N, 1);
    
    ll a, b, c;
    for(int i = 0; i < M + K; i++){
        cin >> a >> b >> c;
        if(a == 1){
            update_tree(1, N, b, c, 1);
            arr[b] = c;
        }
        else if(a == 2) cout << getQuery(1, N, b, c, 1) << "\n";
    }
}
 
int main(){
    fastio
    input();
    solve();
    
    return 0;
}