Educational Codeforces Round 37 (Rated for Div. 2)F. SUM and REPLACE+线段树

题意：给一个数组，两种操作，第一种把[L,R]的数变成这个数的因子个数（这个是log级别的下降），第二种求[L,R]的和

题解：我们发现当数字到1或2后就不会更改，我们用两个线段树，一个维护和，一个维护区间最大值，当区间的最大值小于等于2的时候就可以不用更新了。

#include<bits/stdc++.h>
#include<set>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#define pb push_back
#define ll long long
#define PI 3.14159265
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define eps 1e-7
typedef unsigned long long ull;
const int mod=1e9+7;
const int maxn=3e5+5;
const int root=1e6+7;
using namespace std;
int a[maxn],ma[maxn<<2],n,q,num[root];
ll tree[maxn<<2];
void push(int rt)
{
    ma[rt]=max(ma[rt<<1],ma[rt<<1|1]);
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
    return ;
}
void init()
{
    for(int i=0;i<root;i++)num[i]=1;
    for(int i=2;i<root;i++)
    {
        for(int j=i;j<root;j+=i)
        {
            num[j]++;
        }
    }
}
void built(int l,int r,int rt)
{
    if(l==r)
    {
       tree[rt]=ma[rt]=a[l];
       return ;
    }
    int m=(l+r)/2;
    built(ls);
    built(rs);
    push(rt);
}
void update(int L,int R,int l,int r,int rt)
{
    //if(r<L||l>R)return ;
    if(l==r)
    {
        ma[rt]=num[ma[rt]];
        tree[rt]=num[tree[rt]];return ;
    }
    int m=(l+r)/2;
    if(L<=m&&ma[rt<<1]>2)
        update(L,R,ls);
    if(R>m&&ma[rt<<1|1]>2)
        update(L,R,rs);
    push(rt);
}
ll query(int L,int R,int l,int r,int rt)
{
      //if(r<L||l>R)return 0;
      if(L<=l&&r<=R)
      {
          return tree[rt];
      }
      ll ans=0;
      int m=(l+r)/2;
      if(L<=m)
            ans+=query(L,R,ls);
      if(R>m)
            ans+=query(L,R,rs);
      return ans;
}
int main()
{
    init();
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    built(1,n,1);
    while(q--)
    {
        int op,x,y;
        scanf("%d %d %d",&op,&x,&y);
        if(op==1)
        {
            update(x,y,1,n,1);
        }
        else
        {
            printf("%lld
",query(x,y,1,n,1));
        }
    }
    return 0;
}

Educational Codeforces Round 37 (Rated for Div. 2)F. SUM and REPLACE+线段树

相关推荐