F. SUM and REPLACE codeforces920f(线段树)-蒲公英云

F. SUM and REPLACE codeforces920f(线段树)

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
求一个数的因子个数：https://blog.csdn.net/ii0789789789/article/details/79683286

Let D(x) be the number of positive divisors of a positive integer x. For example, D(2) = 2 (2 is divisible by 1 and 2), D(6) = 4 (6 is divisible by 1, 2, 3 and 6).
You are given an array a of n integers. You have to process two types of queries:

REPLACE l r — for every replace ai with D(ai);
SUM l r — calculate .

Print the answer for each SUM query.
Input

The first line contains two integers n and m (1 ≤ n, m ≤ 3·105) — the number of elements in the array and the number of queries to process, respectively.

The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 106) — the elements of the array.

Then m lines follow, each containing 3 integers ti, li, ri denoting i-th query. If ti = 1, then i-th query is REPLACE li ri, otherwise it’s SUM li ri (1 ≤ ti ≤ 2, 1 ≤ li ≤ ri ≤ n).

There is at least one SUM query.
Output

For each SUM query print the answer to it.
Example
Input
Copy

7 6
6 4 1 10 3 2 4
2 1 7
2 4 5
1 3 5
2 4 4
1 5 7
2 1 7

Output
Copy

30
13
4
22

分析：
这又是一颗线段树。我数组一开始开小了wa。一开始不会求因子个数wa。好菜呀。

势能线段树大都是通过限制条件以达到减少多颗子树的搜索。
例如最大值，次大值的限制。这个题，我们要考虑的限制条件是因子个数，无论多大的树，最大6次操作后，值会变成1。那么我们每个结点都维护一个time值，如果这个结点的访问次数超过了10次，就可以不搜索这个结点的子树了。

#include"stdio.h"
#include"string.h"
#include"math.h"
#include"algorithm"
using namespace std;
typedef long long ll;
int num_factor[1001000];
int n,m,a[5001000],time[5001000];
int val[5001000];
ll sum[5001000];
void Push_up(int id)
{
    sum[id] = sum[id << 1] + sum[id << 1 | 1];
    return ;
}
void Build_Tree(int id,int l,int r)
{
    sum[id] = 0;
    time[id] = 0;
    val[id] = 0;
    if(l == r)
    {
        sum[id] = a[l];
        val[id] = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    Build_Tree(id << 1,l,mid);
    Build_Tree(id << 1 | 1,mid + 1,r);
    Push_up(id);
}
ll Query_sum(int id,int L,int R,int l,int r)
{
    if(l <= L && r >= R)
        return sum[id];
    int mid = (L + R) >> 1;
    ll ans = 0;
    if(l <= mid)
        ans += Query_sum(id << 1,L,mid,l,r);
    if(r > mid)
        ans += Query_sum(id << 1 | 1,mid + 1,R,l,r);
    return ans;
}
void Update(int id,int L,int R,int l,int r)
{
    if(l <= L && r >= R)
    {
        if(time[id] >= 10)
            return ;
        time[id] ++;
    }
    if(L == R)
    {
        //  printf("val[id] = %d num_factor = %d\n",val[id],num_factor[val[id]]);
        val[id] = num_factor[val[id]];
        sum[id] = val[id];
        return ;
    }
    int mid = (L + R) >> 1;
    if(l <= mid)
        Update(id << 1,L,mid,l,r);
    if(r > mid)
        Update(id << 1 | 1,mid + 1,R,l,r);
    Push_up(id);
}
///菜鸡版因子个数 555
void init()
{
    num_factor[1] = 1;
    num_factor[2] = 2;
    num_factor[3] = 2;
    for(int i = 4; i <= 1000000; i ++)
    {
        int n = i;
        int num = 1;
        for(int j = 2; j * j <= n; j ++)
        {
           int cnt = 0;
           while(n % j == 0)
           {
               cnt ++; n = n / j;
           }
           num = num * (cnt + 1);
        }
        if(n != 1)
        {
            num = num * 2;
        }
        num_factor[i] = num;
    }
}
int main()
{
    init();
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i ++)
        scanf("%d",&a[i]);
    Build_Tree(1,1,n);
    for(int i = 1; i <= m; i ++)
    {
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(op == 1)
            Update(1,1,n,x,y);
        if(op == 2)
        {
            printf("%lld\n",Query_sum(1,1,n,x,y));
        }
    }
}