水题加一

如果题目不取模的话，就是一道裸的线段树区间求积。但现在加了取模的话，其实就是第2种操作的时候乘上 的逆元即可。逆元费马小定理就可以。

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const int mod=1e9+7;

int n,m;
ll a[maxn];
struct node{
    int l,r;
    ll w;
}t[maxn<<2];

ll qpow(ll x,ll y)//快速幂求逆元
{
    ll ans=1;
    while(y) 
    {
        if(y&1)ans=(ans*x)%mod;
        y>>=1; x=(x*x)%mod;
    }
    return ans;
}

void pushup(int k)
{
    t[k].w=t[k<<1].w*t[k<<1|1].w%mod;
} 

void build(int k,int l,int r)
{
    t[k].l=l,t[k].r=r;
    if(l==r){t[k].w=a[l];return;}
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    pushup(k);
}

void update(int k,int x,ll y)
{
    if(t[k].l==t[k].r){t[k].w=t[k].w*y%mod;return;}
    int mid=t[k].l+t[k].r>>1;
    if(x<=mid)update(k<<1,x,y);
    else update(k<<1|1,x,y);
    pushup(k);
}

ll query(int k,int l,int r)
{
    int x=t[k].l,y=t[k].r;
    if(l<=x&&y<=r)return t[k].w;
    int mid=x+y>>1;
    ll ans=1;
    if(l<=mid)ans=ans*query(k<<1,l,r)%mod;
    if(mid<r)ans=ans*query(k<<1|1,l,r)%mod;
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)a[i]=1;
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int op,x,y; cin>>op>>x>>y;
        if(op==1)update(1,x,y);
        else if(op==2)update(1,x,qpow(y,mod-2));
        else cout<<query(1,x,y)<<"\n";
    }//全程记得取模就行
    return 0;
}