[线段树][收敛函数][区间修改]

https://cn.vjudge.net/problem/CodeForces-920F

跟上一道HDU的题目很像，也是求快速收敛函数的和，因为有结论n的约数个数期望为sqrt(n)。每次遇到一个数就将其质因数分解然后求约数个数，这里可以开一个1e6的数组把处理过的n存下来，记忆化，就可以省下来很多时间（大概吧呵呵）。另外一个需要注意的点是收敛的终点可能是1也可能是2，我这里的方法是把读入的1全变成2，然后输出的时候减去前缀和差分就行了，因为1是怎么都不会变的，2也是不会变的，这样可以保证正确。

//#include<bits/stdc++.h>
#include
#include
#include
#include

#include
#include
#include
#include
#include
#include
#include

#include
#include
#include
#include
//#include
#define eps (1e-6)
using namespace std;
typedef long long LL;
const int maxn=3e5+100;
//const int MOD=1e9+7;
const int INF=0x4f4f4f4f;
const int maxnode=6e6+5;

LL edu[maxn<<2],addv[maxn<<2];

int ys[1000005];
int getys(int A)
{
    int ta=A;
    if(ys[ta]!=0)
        return ys[A];
    LL ans=1;
    int tmp=0;
    int k=0;
    if(A%2==0)
    {
        tmp=0;
        while(!(A%2))
        {
            tmp++;
            A/=2;
        }
    }
    ans*=(1+tmp);
    for(int i=3;i*i<=A;i+=2)
    {
        if(A%i==0)
        {
            tmp=0;
            while(!(A%i))
            {
                tmp++;
                A/=i ;
            }
            ans*=(1+tmp);
        }
    }
    if(A!=1)
    {
        ans*=2;
    }
    return ys[ta]=ans;
}

void maintain(int o,int l, int r)
{
    int lc=o<<1,rc=(o<<1)+1; if(r>l)
        edu[o]=edu[lc]+edu[rc];
    else
        edu[o]=getys(edu[o]);
}

int pl,pr,pos;
LL v;
void change(int o,int l,int r)
{
    if(l==r)
        edu[o]=v;
    else
    {
        int mid=(l+r)>>1;
        if(pos<=mid)change(o<<1,l,mid);
        else change((o<<1)+1,mid+1,r);
        edu[o]=edu[o<<1]+edu[(o<<1)+1];
    }

}

void update(int o,int l,int r)
{
    if(pl<=l&&r<=pr)
    {
        if(edu[o]==((r-l+1)<<1))//wtf? return ; } if(r>l)
    {
        int mid=(l+r)>>1;
        if(pl<=mid)
            update(o<<1,l,mid); if(pr>mid)
            update((o<<1)+1,mid+1,r);
    }
    maintain(o,l,r);
}

int ql,qr;

LL query(int o,int l,int r)
{
    if(ql<=l&&r<=qr) { return edu[o]; } else if(r>l)
    {
        LL ans=0;
        int mid=(l+r)>>1;
        if(ql<=mid)
            ans+=query(o<<1,l,mid); if(qr>mid)
            ans+=query((o<<1)+1,mid+1,r);
        return ans;
    }
    else
    {
        return edu[o];
    }

}

LL cnt[maxn],su[maxn];

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int n,m,op,a,b;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&v);
        if(v==1)
        {
            v=2;
            cnt[i]=1;
        }
        pos=i;
        change(1,1,n);
    }
    for (int i=1;i<=n;i++)
        su[i]=su[i-1]+cnt[i];
    while(m--)
    {
        scanf("%d%d%d",&op,&a,&b);
        if(op==1)
        {
            pl=a,pr=b;
            update(1,1,n);
        }
        else
        {
            ql=a,qr=b;
            printf("%lld\n",query(1,1,n)-su[b]+su[a-1]);
        }
    }
    return 0;
}

一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

发表回复 取消回复

发表回复取消回复