HDU 5634 Rikka with Phi 线段树

题意：bc round 73 div1 D 中文题面

分析：注意到10^7之内的数最多phi O(log(n))次就会变成1，

因此可以考虑把一段相同的不为1的数缩成一个点，用平衡树来维护。

每次求phi的时候就在平衡树上取出这个区间然后暴力求phi，如果一段数变成了1，

就在平衡树里面删掉它，最后统计答案的时候只要把区间中被删去的1加回答案即可，

时间复杂度O((n + m)logn)

注：平衡树，写起来麻烦（然后其实我也不会写）

但是题解当中说把一段相同的数缩成一个点，就很好

所以用线段树，节点维护区间和以及（当这个区间元素都相同时）维护这个元素

然后操作2和操作3就是普通的线段树应用，区间更新以及区间求和

然后操作1，由于我维护了一整段相同元素的区间，所以更新时，

只要按照区间更新，区间在更新范围内，且节点所管辖区间的元素全部相同的时候，直接修改节点

区间更新就好了，这样的话，时间复杂度不是很高

由于单个元素的范围是1e7，所以先筛一遍欧拉函数

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e7;
const int maxn=3e5+5;
const LL mod = 1e9+7;
int phi[N+50],n,m,T;
int o[maxn<<2],mark[maxn<<2];
LL sum[maxn<<2];
void pushup(int rt)
{
    sum[rt]=sum[rt*2]+sum[rt*2+1];
    if(o[rt*2]==o[rt*2+1]&&o[rt*2])
        o[rt]=o[rt*2];
    else o[rt]=0;
}
void pushdown(int rt,int l,int r)
{
    if(mark[rt])
    {
        int mid=(l+r)>>1;
        sum[rt*2]=1ll*(LL)(mid-l+1)*(LL)(mark[rt]);
        sum[rt*2+1]=1ll*(LL)(r-mid)*(LL)(mark[rt]);
        o[rt*2]=o[rt*2+1]=mark[rt];
        mark[rt*2]=mark[rt*2+1]=mark[rt];
        mark[rt]=0;
    }
}
void build(int rt,int l,int r)
{
    if(l==r)
    {
        scanf("%d",&o[rt]);
        sum[rt]=o[rt];
        return ;
    }
    int mid=(l+r)>>1;
    build(rt*2,l,mid);
    build(rt*2+1,mid+1,r);
    pushup(rt);
}
void op1(int rt,int l,int r,int x,int y)
{
    if(x<=l&&r<=y&&o[rt])
    {
        int tmp=phi[o[rt]];
        o[rt]=mark[rt]=tmp;
        sum[rt]=1ll*(LL)(r-l+1)*(LL)(tmp);
        return;
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)op1(rt*2,l,mid,x,y);
    if(y>mid)op1(rt*2+1,mid+1,r,x,y);
    pushup(rt);
}
int t;
void op2(int rt,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        o[rt]=mark[rt]=t;
        sum[rt]=1ll*(LL)(r-l+1)*(LL)(t);
        return;
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if(x<=mid)op2(rt*2,l,mid,x,y);
    if(y>mid)op2(rt*2+1,mid+1,r,x,y);
    pushup(rt);
}
LL op3(int rt,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
        return sum[rt];
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    LL ans=0;
    if(x<=mid)ans+=op3(rt*2,l,mid,x,y);
    if(y>mid)ans+=op3(rt*2+1,mid+1,r,x,y);
    return ans;
}
int main()
{
    phi[1]=1;
    for(int i=2; i<=N; ++i)
    {
        if(!phi[i])
        {
            for(int j=i; j<=N; j+=i)
            {
                if(!phi[j])
                    phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
        }
    }
    scanf("%d",&T);
    while(T--)
    {
        memset(o,0,sizeof(o));
        memset(mark,0,sizeof(mark));
        scanf("%d%d",&n,&m);
        build(1,1,n);
        while(m--)
        {
            int c,l,r;
            scanf("%d%d%d",&c,&l,&r);
            if(c==2)scanf("%d",&t);
            if(c==1)op1(1,1,n,l,r);
            else if(c==2)op2(1,1,n,l,r);
            else printf("%I64d
",op3(1,1,n,l,r));
        }
    }
    return 0;
}