CodeForces - 920F SUM and REPLACE （线段树）

题意：给N个数M次操作，（1<=N,M<=3e5, 1<=ai<=1e6），1是使[L,R]中的每个元素变成其因子的个数之和；2是求[L,R]区间之和

分析：看上去就很线段树的一题，但是却思考了很久。发现1和2即使对其，也不会改变二者的值。而且一个大于2的数进行多次1操作，也最终会退化到2。

先预处理筛出1e6以内各数的质因子个数和。在线段树的节点中维护两个值：区间和以及区间最大值。在update函数中，如果该区间的最大值不超过2，那么该区间没有更新的必要；若超过2，则递归向下找到那个位置，并更新它。

听起来像是退化成了单点更新线段树，其实打个表能发现每个数的因子个数和不会很大，退化几次就成为2了，所以在更新次数很多的情况下，复杂度并不会很高。

#include<bits/stdc++.h>

using namespace std;

const int maxn=3e5+;

const int INF =0x3f3f3f3f;

const int maxv = 1e6+;

typedef long long LL;

struct SGndoe{

    LL sum;

    LL mx;

}tree[maxn<<];

LL a[maxn];

LL ans[maxv];

void pre()

{

    for(int i=;i<=1e6;++i){

        for(int j=;j<=1e6;j+=i){

            ans[j]++;

        }

    }

}

void pushup(int root)

{

    tree[root].sum =tree[root<<].sum+tree[root<<|].sum;

    tree[root].mx = max(tree[root<<].mx,tree[root<<|].mx);

}

void build(int root,int L,int R){

    if(L==R){

        tree[root].sum = tree[root].mx=a[L];

        return;

    }

    int mid =(L+R)>>;

    build(root<<,L,mid);

    build(root<<|,mid+,R);

    pushup(root);

}

void update(int root,int l,int r,int L,int R)

{

    if(L<=l && R>=r && tree[root].mx<=) return;

    else if(l==r){

        tree[root].sum = ans[tree[root].sum];

        tree[root].mx = tree[root].sum;

        return;

    }

    int mid=(l+r)>>;

    if(L<=mid)update(root<<,l,mid,L,R);

    if(R>mid) update(root<<|,mid+,r,L,R);

    pushup(root);

}

LL query(int root,int l,int r,int L,int R)

{

    if(L<=l&&r<=R) return tree[root].sum;

    int mid=(l+r)>>;

    LL res=;

    if(L<=mid) res+=query(root<<,l,mid,L,R);

    if(mid<R) res+=query(root<<|,mid+,r,L,R);

    return res;

}

int main(){

    int T,N,M,num,t,x;

    int L,R;

    #ifndef ONLINE_JUDGE

        freopen("in.txt","r",stdin);

        freopen("out.txt","w",stdout);

    #endif

    pre();

    int cas=;

    while(scanf("%d%d",&N,&M)==){

        for(int i=;i<=N;++i) scanf("%lld",&a[i]);

        build(,,N);

        int op;

        for(int i=;i<=M;++i){

            scanf("%d%d%d",&op,&L,&R);

            if(op==) update(,,N,L,R);

            else printf("%lld\n",query(,,N,L,R));

        }

    }

    return ;

}

巴特西

CodeForces - 920F SUM and REPLACE （线段树）

最新文章

热门文章