[HDU5634]Rikka with Phi【线段树】

Rikka with Phi

【题目描述】

传送门

【题解】

我们会发现1操作会很快使区间值为1,并且每次修改会使一个区间变成相同的,所以我们可以记一下相同的区间,直接修改就可以了,对于不同的,那么继续递归修改。

代码如下

#include<cstdio>
using namespace std;
typedef long long LL;
const int MAXN=300005,MAXM=10000000;
int T,n,m,a[MAXN],p[MAXM+5],phi[MAXM+5];
LL Tre[MAXN<<2],Same[MAXN<<2];
bool vis[MAXM+5];
#include<cctype>
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret*10+ch-48);
    return f?ret:-ret;
}
void make_p(){
    vis[0]=vis[1]=1;phi[1]=1;
    for(int i=2;i<=MAXM;i++){
        if(!vis[i]) p[++p[0]]=i,phi[i]=i-1;
        for(int j=1;j<=p[0]&&p[j]*i<=MAXM;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}
            phi[i*p[j]]=phi[i]*(p[j]-1);
        }
    }
}
void PushUp(int rt){Tre[rt]=Tre[rt<<1]+Tre[rt<<1|1];Same[rt]=(Same[rt<<1]==Same[rt<<1|1]?Same[rt<<1]:-1);}
void Build(int rt,int L,int R){
    if(L==R){Tre[rt]=Same[rt]=a[L];return;}
    int mid=(R+L)>>1;
    Build(rt<<1,L,mid);Build(rt<<1|1,mid+1,R);
    PushUp(rt);
}
void PushDown(int rt,int Ln,int Rn){
    if(Same[rt]!=-1){
        Tre[rt<<1]=Same[rt]*Ln,Tre[rt<<1|1]=Same[rt]*Rn;
        Same[rt<<1]=Same[rt<<1|1]=Same[rt];
    }
}
void Updata1(int rt,int L,int R,int l,int r){
    if(l<=L&&R<=r&&Same[rt]!=-1){Same[rt]=phi[Same[rt]],Tre[rt]=Same[rt]*(R-L+1);return;}
    int mid=(R+L)>>1;PushDown(rt,mid-L+1,R-mid);
    if(l<=mid) Updata1(rt<<1,L,mid,l,r);
    if(mid<r) Updata1(rt<<1|1,mid+1,R,l,r);
    PushUp(rt);
}
void Updata2(int rt,int L,int R,int l,int r,int p){
    if(l<=L&&R<=r){Same[rt]=p,Tre[rt]=(LL)p*(R-L+1);return;}
    int mid=(R+L)>>1;PushDown(rt,mid-L+1,R-mid);
    if(l<=mid) Updata2(rt<<1,L,mid,l,r,p);
    if(mid<r) Updata2(rt<<1|1,mid+1,R,l,r,p);
    PushUp(rt);
}
LL Query(int rt,int L,int R,int l,int r){
    if(l<=L&&R<=r) return Tre[rt];
    int mid=(R+L)>>1;LL Ans=0;PushDown(rt,mid-L+1,R-mid);
    if(l<=mid) Ans+=Query(rt<<1,L,mid,l,r);
    if(mid<r) Ans+=Query(rt<<1|1,mid+1,R,l,r);
    return Ans;
}
int main(){
    make_p();T=read();
    while(T--){
        n=read(),m=read();
        for(int i=1;i<=n;i++) a[i]=read();
        Build(1,1,n);
        while(m--){
            int typ=read(),L=read(),R=read();
            if(typ==1) Updata1(1,1,n,L,R);else
            if(typ==2) Updata2(1,1,n,L,R,read());else printf("%lld\n",Query(1,1,n,L,R));
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部