(11505) 구간 곱 구하기

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

단계별로 풀어보기

44단계(세그먼트 트리 1) 2번째

 

 

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define p 1000000007

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, k;
  
  cin >> n >> m >> k;
  
  int treesize= (1<<(((int)ceil(log2(n)))+1));
  vector<long> v(n+1), segtree(treesize);
  
  for(int i=1;i<=n;i++)  cin >> v[i];
  
  auto init= [&](auto self, int s, int e, int node) -> void {
    if(s==e){
      segtree[node]= v[s];
    }else{
      self(self, s, s+(e-s)/2, node*2);
      self(self, s+(e-s)/2+1, e, node*2+1);
      segtree[node]= (segtree[node*2]*segtree[node*2+1])%p;
    }
  };
  
  auto update= [&](auto self, int s, int e, int node, int idx, long val) -> void {
    if(idx<s||e<idx)  return;
    
    if(s==e){
      v[idx]= val;
      segtree[node]= val;
    }else{
      self(self, s, s+(e-s)/2, node*2, idx, val);
      self(self, s+(e-s)/2+1, e, node*2+1, idx, val);
      segtree[node]= (segtree[node*2]*segtree[node*2+1])%p;
    }
  };
  
  auto query= [&](auto self, int s, int e, int node, int l, int r) -> long {
    if(r<s||e<l)  return 1;
    
    if(l<=s&&e<=r){
      return segtree[node];
    }else{
      long lres= self(self, s, s+(e-s)/2, node*2, l, r);
      long rres= self(self, s+(e-s)/2+1, e, node*2+1, l, r);
      return (lres*rres)%p;
    }
  };
  
  init(init, 1, n, 1);
  
  for(int i=0;i<m+k;i++){
    long a, b, c;
    
    cin >> a >> b >> c;
    
    if(a==1)  update(update, 1, n, 1, b, c);
    else  cout << query(query, 1, n, 1, b, c) << "\n";
  }
  
  return 0;
}