F 发电
题目：
链接：https://www.nowcoder.com/acm/contest/136/F
来源：牛客网时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
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）。示例2备注:
对于100%的测试数据：
1 ≤ n, m ≤ 1000000
1 ≤ 神力水晶等级 ≤ 100000
数据量较大，注意使用更快的输入输出方式。
思路：
线段树维护区间乘积即可，注意除法要取逆元。
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int MAXN = 1e6+300; const ll mod = 1e9+7; struct Node{ int l,r; ll val; }tree[MAXN*4]; ll qkm(ll a, ll n){ ll ans =1; a=a%mod; while(n){ if(n&1)ans = ans*a%mod; a = a*a%mod; n>>=1; } return ans; } int a[MAXN]; void build(int l,int r,int k){ tree[k].l=l; tree[k].r=r; if(l==r){ tree[k].val = a[l]; return; } int mid = (l+r)/2; build(l,mid,2*k); build(mid+1,r,2*k+1); tree[k].val = (tree[2*k].val*tree[2*k+1].val)%mod; } void update(int pos,ll v,int k,int type){ if(tree[k].l==pos&&tree[k].r==pos){ if(type==1) ///镶嵌水晶 tree[k].val =tree[k].val*v%mod; else if(type==2) ///拆掉水晶 tree[k].val = tree[k].val*qkm(v,mod-2)%mod; /// 除法要取逆元 return; } int mid = (tree[k].l+tree[k].r)/2; if(pos<=mid)update(pos,v,2*k,type); else update(pos,v,2*k+1,type); tree[k].val= (tree[2*k].val*tree[2*k+1].val)%mod; } ll query(int l,int r,int k){ if(l<=tree[k].l&&tree[k].r<=r){ return tree[k].val; }else{ int mid = (tree[k].l+tree[k].r)/2; if(l>mid) return query(l,r,2*k+1); else if(r<=mid) return query(l,r,2*k); else return query(l,r,2*k)* query(l,r,2*k+1)%mod; } } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ a[i] = 1; } build(1,n,1); while(m--){ int x,y,z; scanf("%d%d%d",&x,&y,&z); if(x==3){ printf("%lld ",query(y,z,1)); }else{ update(y,(ll)z,1,x); } } return 0; }