CF920F SUM and REPLACE

CF920F SUM and REPLACE

Description

链接

Solution

显然一个数最多修改次数有限，考虑暴力修改，维护最大值判断还需要修改不

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 300000 + 10;

inline long long read()
{
    long long f=1,x=0;
    char ch;
    do
    {
        ch=getchar();
        if(ch=='-') f=-1;
    }while(ch<'0'||ch>'9');
    do
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }while(ch>='0'&&ch<='9');
    return f*x;
}

int n;

long long a[MAXN];
long long d[MAXN * 10];

struct node
{
    int l;
    int r;
    long long sum;
    long long maxn;
    inline int mid()
    {
        return (l+r)>>1;
    }
};

node tree[MAXN*4];

#define lc o<<1
#define rc o<<1|1

inline void build(int o,int l,int r)
{
    tree[o].l=l;
    tree[o].r=r;
    if(l==r) 
    {
        tree[o].sum=tree[o].maxn=a[l];
        return;
    }
    else
    {
        int mid = tree[o].mid();
        build(lc,l,mid);
        build(rc,mid+1,r);
        tree[o].sum=tree[lc].sum+tree[rc].sum;
        tree[o].maxn=max(tree[lc].maxn,tree[rc].maxn);
        return;
    }
}

inline void change(int o,int x,int y)
{
    int l = tree[o].l;
    int r = tree[o].r;
    if(l==r)
    {
        tree[o].sum=d[tree[o].sum];
        tree[o].maxn=d[tree[o].maxn];
        return;
    }
    int mid = tree[o].mid();
    if(x<=mid&&tree[lc].maxn>2) change(lc,x,y);
    if(mid<y&&tree[rc].maxn>2) change(rc,x,y);
    tree[o].maxn  = max(tree[lc].maxn,tree[rc].maxn);
    tree[o].sum  = tree[lc].sum+tree[rc].sum;
}

inline long long query(int o,int x,int y)
{
    int l = tree[o].l;
    int r = tree[o].r;
    if(x<=l&&y>=r) return tree[o].sum;
    if(y<l||r<x) return 0;
    else
    {
        return query(lc,x,y)+query(rc,x,y);
    }
}

int main()
{
    n=read();
    int m=read();
    long long MAXA = 0;
    for(int i=1;i<=n;i++)
        a[i]=read(),MAXA = max(MAXA,a[i]);
    build(1,1,n);
    for(int i=1;i<=sqrt(MAXA);i++)
    {
        for(int j=i*i;j<=MAXA;j+=i)
        {
            if(j/i == i) 
            {
                d[j] += 1;
        //        cout << j << " " <<i << " " <<d[j] << endl;
                continue;
            }
            d[j] += 2;        
    //        cout << j << " " << i <<" " <<d[j] << endl;
        }
    }
//    for(int i=1;i<=10;i++) cout << d[i] << " ";
//    cout << endl;

    for(int i=1;i<=m;i++)
    {
        int k,x,y;
        k=read();
        x=read();
        y=read();
        if(x>y) swap(x,y);
        if(k==1)
        {
            change(1,x,y);
        }
        else
        cout<<query(1,x,y)<<endl;
    }
}