F. SUM and REPLACE codeforces920f(线段树)

╰+哭是因爲堅強的太久メ 2021-11-01 20:02 274阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。  
求一个数的因子个数：[https://blog.csdn.net/ii0789789789/article/details/79683286][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));
            }
        }
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/
[https_blog.csdn.net_ii0789789789_article_details_79683286]: https://blog.csdn.net/ii0789789789/article/details/79683286