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

質問する

6個の数がある.しかし,中間には数の変更が頻繁に発生し,中間にはある部分の積が要求される.1,2,3,4,5があれば,3番目の数を6に変更し,2番目から5番目に乗じて240を出力すればよい.そしてこの状態で、5番目の数を2に変えて、3番目から5番目の数まで積を求めると、48になります.

入力

第1行は数の個数N(1≦N≦1000000)とM(1≦M≦10000),K(1≦K≦10000)を与える.Mは発生数の変更の回数であり,Kは区間積を求める回数である.そして、2行目からN+1行目までN個の数が与えられる.次に、N+2行からN+M+K+1行に3つの整数a,b,cを与え、aが1であればbをcに変換し、aが2であればbからcの積を求め、出力する.
入力したすべての数はゼロ以上、1000000以下の整数です.

しゅつりょく

1行目からK行で求めた区間の積を10000007で割って残りの部分を出力します.

サンプルI/O

入力

例1

5 2 2
1
2
3
4
5
1 3 6
2 2 5
1 5 2
2 3 5

例出力1

240
48

入力

例2

5 2 2
1
2
3
4
5
1 3 0
2 2 5
1 3 6
2 2 5

例出力2

0
240

Solution

#include <iostream>
#define ll long long
#define MAX 1000001
#define MOD 1000000007
using namespace std;

ll arr[MAX];
ll tree[4 * MAX];

ll init(int start, int end, int node){
    if(start == end) return tree[node] = arr[start];
    int mid = (start + end) / 2;
    return tree[node] = (init(start, mid, node * 2) % MOD) * (init(mid + 1, end, node * 2 + 1) % MOD); 
}

ll mult(int start, int end, int left, int right, int node){
    if(left > end || right < start) return 1;
    if(left <= start && end <= right) return tree[node];
    int mid = (start+end)/ 2;
    return (mult(start, mid, left, right, node * 2) % MOD) * (mult(mid + 1, end, left, right, node * 2 + 1) % MOD);
}

ll update(int start, int end, int node, int index, ll diff){
    if(index < start || index > end) return tree[node];
    if(start == end) return tree[node] = diff;
    int mid = (start + end) / 2;
    return tree[node] = (update(start, mid, node * 2, index, diff) % MOD) * (update(mid+1, end, node * 2 + 1, index, diff) % MOD);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, M, K; cin >> N >> M >> K;
    for(int i = 0; i < N; i++) cin >> arr[i];
    init(0, N-1, 1);
    int a, b; ll c;
    for(int i = 0; i < M + K; i++){
        cin >> a >> b >> c;
        if(a == 1){
            int index = b - 1;
            update(0, N - 1, 1, index, c);
        }
        else if (a == 2){
            cout << mult(0, N - 1, b-1, c-1, 1) % MOD << '\n';
        }
    }
}

区間和を求めるコードを分解すればいいです.
重要なことがあるとすれば,この値は非常に大きいので,中間のモジュール化演算が必要である.
この部分を見逃すと、想像以上に解けやすく、なぜダメなのかという泥沼にはまります.