牛客小白月赛6 F 发电树状数组单点更新求区间乘积模板-白红宇

牛客小白月赛6 F 发电树状数组单点更新求区间乘积模板

阅读量：6166 次

发布时间：2019-06-21

本文共 2018 字，大约阅读时间需要 6 分钟。

链接：

来源：牛客网

HA实验是一个生产、提炼“神力水晶”的秘密军事基地，神力水晶可以让机器的工作效率成倍提升。

HA实验基地有n台发电机，标号为1-n，每台发电机的发电效率为1。

为了满足基地的用电需求，HtBest会在某台发电机上镶嵌一个等级为i的神力水晶，该发电机的发电效率是镶嵌神力水晶之前的i倍，一个发电机可以同时镶嵌多个神力水晶。

但是神力水晶有时还有别的用处，HtBest会拆掉某台发电机之前镶嵌上的一个神力水晶（设等级为i），发电机效率降为拆掉神力水晶前的1/i。

HtBest有时想知道第l到r台发电机的总发电效率为多少。

输入描述:

第一行有2个正整数n，m，分别表示发电机数量和操作数。 接下来m行，每行有3个正整数，x, y, z。 x=1时，HtBest镶嵌为第y台发电机镶嵌了一个等级为z的神力水晶， x=2时，HtBest为第y台发电机拆掉了一个等级为z的神力水晶， x=3时，HtBest想知道[y,z]的发电机效率的乘积。

输出描述:

对于每个x=3的操作，输出一行，表示[y,z]的发电机的效率的乘积。 由于输出过大，你需要对输出结果模1000000007（1e9+7）。

示例1

输入

4 41 2 33 1 42 2 33 1 4

输出

说明

操作1之后，每台发电机效率：1 3 1 1 操作3之后，每台发电机效率：1 1 1 1

示例2

输入

4 41 2 21 2 31 3 43 1 4

输出

说明

操作1之后，每台发电机效率：1 2 1 1 操作2之后，每台发电机效率：1 6 1 1 操作3之后，每台发电机效率：1 6 4 1

备注:

对于100%的测试数据： 1 ≤ n, m ≤ 1000000 1 ≤ 神力水晶等级 ≤ 100000 数据量较大，注意使用更快的输入输出方式。 分析：一个单点更新然后求区间乘积的树状数组的板子题，除的地方改成乘法逆元 AC代码：

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define ls (r<<1)#define rs (r<<1|1)#define debug(a) cout << #a << " " << a << endlusing namespace std;typedef long long ll;const ll maxn = 1e6+10;const double eps = 1e-8;const ll mod = 1e9 + 7;const int inf = 0x3f3f3f3f;const double pi = acos(-1.0);ll n, q, a[maxn];ll qow( ll a, ll b ) { ll ans = 1; while(b) { if(b&1) { ans = ans*a%mod; } a = a*a%mod; b /= 2; } return ans;}ll lowbit( ll x ) { return x&(-x);}void update( ll id, ll x ) { while( id <= n ) { a[id] = a[id]*x%mod; id += lowbit(id); }}ll query( ll id ) { ll ans = 1; while( id > 0 ) { ans = ans*a[id]%mod; id -= lowbit(id); } return ans;}int main() { ios::sync_with_stdio(0); cin >> n >> q; for( ll i = 1; i <= n; i ++ ) { a[i] = 1; } ll x, y, z; while( q -- ) { cin >> x >> y >> z; if( x == 1 ) { update(y,z); } else if( x == 2 ) { update(y,qow(z,mod-2)); } else if( x == 3 ) { ll ans = query(z)*qow(query(y-1),mod-2)%mod; cout << ans << endl; } } return 0;}

转载于:https://www.cnblogs.com/l609929321/p/9524686.html

你可能感兴趣的文章