CF1114F Please, another Queries on Array?

欧拉函数+线段树

维护区间乘积、区间质因子的或

#include <iostream>

#include <cstring>

#include <algorithm>

#include <bitset>

#define int long long

using namespace std;

const int N = 4e5+10,M = 100;

const int mod=1e9+7;

int n,m,prime[N],st[N],cnt,w[N],inv[N];

struct Node{

    int l,r;

    int v,mul;

    bitset<M> p,lzp;

}tr[N*4];

int qmi(int a,int b){

    int res=1%mod;

    while(b){

        if(b&1) res=res*a%mod;

        a=a*a%mod;

        b>>=1;

    }

    return res;

}

void init(int n){

    for(int i=2;i<=n;i++){

        if(!st[i]) prime[cnt++]=i;

        for(int j=0;i*prime[j]<=n;j++){

            st[i*prime[j]]=1;

            if(i%prime[j]==0) break;

        }

    }

}

void pushup(Node &u,Node &l,Node &r){

    u.v=l.v*r.v%mod;

    u.p=l.p|r.p;

}

void pushup(int u){

    pushup(tr[u],tr[u<<1],tr[u<<1|1]);

}

void pushdown(int x){

    auto &u=tr[x],&l=tr[x<<1],&r=tr[x<<1|1];

    l.v=l.v*qmi(u.mul,l.r-l.l+1)%mod;

    r.v=r.v*qmi(u.mul,r.r-r.l+1)%mod;

    l.mul=l.mul*u.mul%mod;

    r.mul=r.mul*u.mul%mod;

    l.p|=u.lzp;

    r.p|=u.lzp;

    l.lzp|=u.lzp;

    r.lzp|=u.lzp;

    u.mul=1,u.lzp=0;

}

void build(int u,int l,int r){

    if(l==r){

        bitset<M> p;

        for(int i=0;i<cnt;i++)

            if(w[r]%prime[i]==0)

                p[i]=1;

        tr[u]={l,r,w[r],1,p};

        return ;

    }

    tr[u]={l,r,0,1};

    int mid=l+r>>1;

    build(u<<1,l,mid),build(u<<1|1,mid+1,r);

    pushup(u);

}

void update(int u,int l,int r,int k,int t){

    if(tr[u].l>=l&&tr[u].r<=r){

        tr[u].v=tr[u].v*qmi(k,tr[u].r-tr[u].l+1)%mod;

        tr[u].mul=tr[u].mul*k%mod;

        tr[u].p|=t;

        tr[u].lzp|=t;

        return ;

    }

    pushdown(u);

    int mid=tr[u].l+tr[u].r>>1;

    if(l<=mid) update(u<<1,l,r,k,t);

    if(mid<r) update(u<<1|1,l,r,k,t);

    pushup(u);

}

Node query(int u,int l,int r){

    if(tr[u].l>=l&&tr[u].r<=r) return tr[u];

    pushdown(u);

    int mid=tr[u].l+tr[u].r>>1;

    if(r<=mid) return query(u<<1,l,r);

    else if(l>mid) return query(u<<1|1,l,r);

    Node res,a=query(u<<1,l,r),b=query(u<<1|1,l,r);

    pushup(res,a,b);

    return res;

}

signed main(){

    init(300);

    for(int i=0;i<cnt;i++)

        inv[i]=(prime[i]-1)*qmi(prime[i],mod-2)%mod;

    cin>>n>>m;

    for(int i=1;i<=n;i++) cin>>w[i];

    build(1,1,n);

    while(m--){

        char op[10];

        int l,r,k;

        cin>>op>>l>>r;

        if(op[0]=='M'){

            int x;

            cin>>x;

            int p=0;

            for(int i=0;i<cnt;i++)

                if(x%prime[i]==0)

                    p|=(1ll)<<i;

            update(1,l,r,x,p);

        }

        else{

            Node res=query(1,l,r);

            int sum=res.v;

            for(int i=0;i<cnt;i++)

                if(res.p[i])

                    sum=sum*inv[i]%mod;

            cout<<sum<<endl;

        }

    }

    

    return 0;

}