题目概述

有一个序列 $\{a_n\}$ ，现在有三种操作：1.令 $i\in[L,R],a_i=\varphi(a_i)$ 。2.令 $i\in[L,R],a_i=x$ 。3.询问区间和。

解题报告

吉利的小清新线段树，做区间取 $\varphi$ 的时候如果当前节点全部相等就直接当成区间覆盖，否则继续递归，因为一个数取 $log_2a_i$ 次 $\varphi$ 就会变成 $1$ ，所以每个点只会被改 $O(log_2a_i)$ 次，而且另外一种区间覆盖也是修改成一样的所以复杂度很正常。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=300000,maxa=10000000;

int te,n,m,a[maxn+5],p[maxa+5],phi[maxa+5];bool pri[maxa+5];
int l[(maxn<<2)+5],r[(maxn<<2)+5],MIN[(maxn<<2)+5],MAX[(maxn<<2)+5],tag[(maxn<<2)+5];LL sum[(maxn<<2)+5];

inline void Make(){
    pri[0]=pri[1]=true;phi[1]=1;
    for (int i=2;i<=maxa;i++){
        if (!pri[i]) p[++p[0]]=i,phi[i]=i-1;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=maxa;j++)
            if (i%p[j]) phi[t]=phi[i]*phi[p[j]],pri[t]=true; else {phi[t]=phi[i]*p[j];pri[t]=true;break;}
    }
}
inline void Pushup(int p) {MIN[p]=min(MIN[p<<1],MIN[p<<1|1]);MAX[p]=max(MAX[p<<1],MAX[p<<1|1]);}
void Build(int L,int R,int p=1){
    l[p]=L;r[p]=R;tag[p]=0;if (L==R) {sum[p]=MIN[p]=MAX[p]=a[L];return;}int mid=L+(R-L>>1);
    Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);Pushup(p);sum[p]=sum[p<<1]+sum[p<<1|1];
}
inline void Addtag(int p,int x) {MIN[p]=MAX[p]=tag[p]=x;sum[p]=(LL)(r[p]-l[p]+1)*x;}
inline void Pushdown(int p) {if (tag[p]) Addtag(p<<1,tag[p]),Addtag(p<<1|1,tag[p]),tag[p]=0;}
void Phi(int L,int R,int p=1){
    if (L==l[p]&&r[p]==R&&MIN[p]==MAX[p]) return Addtag(p,phi[MIN[p]]);int mid=l[p]+(r[p]-l[p]>>1);
    Pushdown(p);if (R<=mid) Phi(L,R,p<<1); else if (L>mid) Phi(L,R,p<<1|1);
    else Phi(L,mid,p<<1),Phi(mid+1,R,p<<1|1);Pushup(p);sum[p]=sum[p<<1]+sum[p<<1|1];
}
inline void Cover(int L,int R,int k,int p=1){
    if (L==l[p]&&r[p]==R) return Addtag(p,k);int mid=l[p]+(r[p]-l[p]>>1);
    Pushdown(p);if (R<=mid) Cover(L,R,k,p<<1); else if (L>mid) Cover(L,R,k,p<<1|1);
    else Cover(L,mid,k,p<<1),Cover(mid+1,R,k,p<<1|1);Pushup(p);sum[p]=sum[p<<1]+sum[p<<1|1];
}
inline LL Sum(int L,int R,int p=1){
    if (L==l[p]&&r[p]==R) return sum[p];int mid=l[p]+(r[p]-l[p]>>1);Pushdown(p);
    if (R<=mid) return Sum(L,R,p<<1); else if (L>mid) return Sum(L,R,p<<1|1);
    else return Sum(L,mid,p<<1)+Sum(mid+1,R,p<<1|1);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (Make(),scanf("%d",&te);te;te--){
        scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&a[i]);Build(1,n);
        for (int tp,x,y,z;m;m--){
            scanf("%d%d%d",&tp,&x,&y);
            if (tp==1) Phi(x,y); else if (tp==3) printf("%lld\n",Sum(x,y));
            else scanf("%d",&z),Cover(x,y,z);
        }
    }return 0;
}