[백준/BOJ/11505] 구간 곱 구하기

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

11505번: 구간 곱 구하기

세그먼트 트리이고, long long 처리에 유의해야 한다.

#include <iostream>
using namespace std;
typedef long long ll;
#define rint register int
const int MOD = 1e9+7;
const int MAX = 1e6+1;
int N,M,K,arr[MAX];
ll tree[MAX*3];
void init(int node,int start,int end){
	if(start==end){
		tree[node] = 1LL*arr[start];
	}else{
		init(node*2,start,(start+end)/2);
		init(node*2+1,(start+end)/2+1,end);
		tree[node] = (tree[node*2]*tree[node*2+1])%MOD;
	}
}
void update(int node,int start,int end,int index,int change){
	if(index < start || index > end) return;
	if(start==end){
		arr[index]=change;
		tree[node]=1LL*change;
		return;
	}
	update(node*2,start,(start+end)/2,index,change);
	update(node*2+1,(start+end)/2+1,end,index,change);
	tree[node] = (tree[node*2]*tree[node*2+1])%MOD;
}
ll query(int node,int start,int end,int left,int right){
	if(left>end || right<start) return -1LL;
	if(left<=start && end<=right) return tree[node];
	ll lm = query(node*2,start,(start+end)/2,left,right);
	ll rm = query(node*2+1,(start+end)/2+1,end,left,right);
	if(lm==-1LL) return rm;
	if(rm==-1LL) return lm;
	return (lm*rm)%MOD;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin>>N>>M>>K;
	for(rint i=1;i<=N;++i) cin>>arr[i];
	init(1,1,N);
	for(rint i=0;i<M+K;++i){
		int a; cin>>a;
		if(a==1){
			int index,change;
			cin>>index>>change;
			update(1,1,N,index,change);
		}else{
			int left,right;
			cin>>left>>right;
			cout<<query(1,1,N,left,right)<<"\n";
		}
	}
	return 0;
}