[ BOJ 백준 11505번 - 구간 곱 구하기 ] 해설 및 코드

https://www.acmicpc.net/problem/11505

 

 

목적

백준 2042 - 구간 합 구하기에 이어 query부분을 조금 수정하여 구간 곱을 구해보자.

 

접근법

1. 세그먼트 트리구현 기본 예제이다. (위 게시물 참고할 것)

 

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
#define fr(i,l,r) for(int i=l;i>=r;--i)
using namespace std;
typedef long long ll;
 
const int mod=1e9+7;
int n,offset,s[1<<21];
 
void update(int i,int val){
    s[i+=offset]=val;
    while(i>>=1)s[i]=((ll)s[i<<1]*s[(i<<1)|1])%mod;
}
 
int query(int i,int j){
    int ret=1;
    i+=offset;j+=offset;
    while(i<=j){
        if(i&1)ret=((ll)ret*s[i++])%mod;
        if(!(j&1))ret=((ll)ret*s[j--])%mod;
        i>>=1;j>>=1;
    }
    return ret;
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int m,k;cin>>n>>m>>k;
    
    offset=1;
    while(offset<n)offset<<=1;
    --offset;
    
    f(i,1,n)cin>>s[i+offset];
    f(i,n+1,offset+1)s[i+offset]=1;
    fr(i,offset,1)s[i]=((ll)s[i<<1]*s[(i<<1)|1])%mod;
    
    m+=k;
    while(m--){
        int a,b,c;cin>>a>>b>>c;
        if(a==1)update(b,c);
        else cout<<query(b,c)<<'\n';
    }
    
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.