CodeForces-1114F Another Queries on Array?

传送门：CodeForces-1114F

思路分析

如果对于每次询问都单独计算欧拉函数值肯定会超时
因为都是300以下的数字，素数只有62个，所以可以通过状压的方式，统计区间内的素数个数

样例输入

4 4
5 9 1 2
TOTIENT 3 3
TOTIENT 3 4
MULTIPLY 4 4 3
TOTIENT 4 4

样例输出

1
1
2

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e6+5;

int prim[333],ok[333],state[333],inv[333],a[N],cnt;

struct node {
    int l,r,mid,len,sum,st,lst,mul;
} tree[N<<2];

ll qmul(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void init(int n) {
    memset(ok,true,sizeof(ok));
    ok[0]=ok[1]=false;
    for(int i=2; i<=n; i++) {
        if(ok[i]) {
            prim[cnt++]=i;
            for(int j=i*i; j<=n; j+=i) {
                ok[j]=false;
            }
        }
    }
    inv[1]=1;
    for(int i=2; i<=n; i++) inv[i]=mod-mod/i*inv[mod%i]%mod;
    for(int i=1; i<=n; i++) {
        for(int j=0; j<cnt; j++) {
            if(i<prim[j]) break;
            if(i%prim[j]==0) state[i]+=(1LL<<j);
        }
    }
}

void pp(int x) {
    tree[x].sum=(tree[rs].sum*tree[ls].sum)%mod;
    tree[x].st=tree[rs].st|tree[ls].st;
}

void build(int x,int l,int r) {
    tree[x].l=l;
    tree[x].r=r;
    tree[x].mid=l+r>>1;
    tree[x].len=r-l+1;
    tree[x].mul=1;
    if(l==r) {
        tree[x].st=state[a[l]];
        tree[x].sum=a[l];
        return ;
    }
    int mid=tree[x].mid;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pp(x);
}

void pd(int x) {
    tree[rs].mul=tree[rs].mul*tree[x].mul%mod;
    tree[ls].mul=tree[ls].mul*tree[x].mul%mod;

    tree[rs].lst|=tree[x].lst;
    tree[ls].lst|=tree[x].lst;

    tree[rs].sum=tree[rs].sum*qmul(tree[x].mul,tree[rs].len)%mod;
    tree[ls].sum=tree[ls].sum*qmul(tree[x].mul,tree[ls].len)%mod;

    tree[rs].st|=tree[x].lst;
    tree[ls].st|=tree[x].lst;

    tree[x].lst=0;
    tree[x].mul=1;
}

void update(int x,int l,int r,int val) {
    if(l<=tree[x].l && tree[x].r<=r) {
        tree[x].sum=tree[x].sum*qmul(val,tree[x].len)%mod;
        tree[x].mul=tree[x].mul*val%mod;
        tree[x].lst|=state[val];
        tree[x].st|=state[val];
        return ;
    }
    int mid=tree[x].mid;
    pd(x);
    if(l<=mid) update(ls,l,r,val);
    if(r>mid) update(rs,l,r,val);
    pp(x);
}

node query(int x,int l,int r) {
    if(l<=tree[x].l&&tree[x].r<=r)
        return tree[x];
    pd(x);
    int mid=tree[x].mid;
    if(r<=mid) return query(ls,l,r);
    if(l>mid) return query(rs,l,r);
    else if(l<=mid && r>mid) {
        node lson=query(ls,l,r);
        node rson=query(rs,l,r);
        node ans;
        ans.sum=lson.sum*rson.sum%mod;
        ans.st=lson.st|=rson.st;
        return ans;
    }
}

signed main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    init(300);
    int n,q;
    cin>>n>>q;
    for(int i=1; i<=n; i++) cin>>a[i];
    build(1,1,n);
    while(q--) {
        string op;
        int l,r;
        cin>>op>>l>>r;
        if(op[0]=='M') {
            int x;
            cin>>x;
            update(1,l,r,x);
        } else {
            node now=query(1,l,r);
            ll ans=now.sum;
            for(int i=0; i<cnt; i++)
                if(now.st&(1LL<<i)) ans=ans*(prim[i]-1)%mod*inv[prim[i]]%mod;
            cout<<ans<<endl;

        }
    }




    return 0;
}
&nbsp;