发电 树状数组 逆元

description：

有n个发电机 开始效率均为1 对应有三种操作 1.给效率翻i倍 2.给效率翻1/i倍 3.查询区间内效率乘积

solution：

n为1e6 看到求区间操作容易想到用树状数组或者线段树维护区间乘积 存在1/i倍的情况用逆元处理 模数是质数采用快速幂求逆元即可

code:

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int N = 1000005;

const LL mod = 1e9 + 7;
int n, m ;
LL c[N];

LL quickpow(LL a,LL b){
    LL res  = 1;

    while(b){
        if(b & 1){
            res = res * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }

    return res;
}

LL lowbit(LL x){
    return x & (-x);
}

void update(LL i,LL x){
    for(;i <= n;i += lowbit(i)){
        c[i] = c[i] * x % mod;
    }
}

LL query(LL i){
    LL res = 1;
    for(;i > 0;i -= lowbit(i)){
        res = res * c[i] % mod;
    }
    return res;
}

int main(){
    ios::sync_with_stdio(0);

    cin >> n >> m;

    for(int i = 0;i <= n;i ++){
        c[i] = 1;
    }
    while(m --){
        int x,y,z;
        cin >> x >> y >> z;

        if(x == 1){
            update(y,z);
        }else if(x ==2){
            update(y,quickpow(z,mod - 2)%mod);
        }else{
            cout << query(z) * quickpow(query(y - 1),mod - 2) % mod << '\n';
        }
    }

    return 0;
}