【牛客小白月赛6】F 发电

题目地址：https://www.nowcoder.com/acm/contest/136/F
树状数组、快速幂、逆元的模板运用；
 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4  
 5 #define LL long long
 6 #define lowbit(x) x&-x
 7 const int N = 1e6+5;
 8 const LL MOD = 1e9+7;
 9 int n, m;
10 LL sum[N];
11  
12 void read(int &x) {
13     int f = 1; x = 0;
14     char ch = getchar();
15     
16     while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
17     while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
18     x *= f;
19 }
20  
21 LL quick_pow(LL a, LL k)
22 {
23     LL tmp=1;
24     while(k) {
25         if(k&1)
26             tmp = tmp*a%MOD;
27         a = a*a%MOD;
28         k>>=1;
29     }
30     return tmp;
31 }
32  
33 LL find(LL b)
34 {
35     LL sum1=1;
36     for(int i=b; i; i-=lowbit(i))
37         sum1 = sum1*sum[i]%MOD;
38     return sum1;
39 }
40  
41 int main()
42 {
43     read(n); read(m);
44     for(int i=1; i<=n; i++) sum[i]=1;
45     
46     for(int x,y,z,t=0; t<m; t++) {
47         read(x); read(y); read(z);
48          
49         if(x == 1) {
50             for(int i=y; i<=n; i+=lowbit(i))
51                 sum[i] = sum[i]*z%MOD;
52         }
53         else if(x == 2) {
54             LL inv = quick_pow(z, MOD-2);
55             for(int i=y; i<=n; i+=lowbit(i))
56                 sum[i] = sum[i]*inv%MOD;
57         }
58         else if(x == 3) {
59             LL ans = find(z)*quick_pow(find(y-1), MOD-2);
60             ans = (ans%MOD + MOD)%MOD;
61             printf("%lld
", ans);
62         }
63     }
64     
65     return 0;
66 }