HDU 5634 Rikka with Phi (线段树)

Problem Description

Rikka and Yuta are interested in Phi function (which is known as Euler's totient function). Yuta gives Rikka an array  of positive integers, then Yuta makes  queries.   There are three types of queries:  Change  into , for all . Change  into , for all . Sum up , for all . Help Rikka by computing the results of queries of type 3.

Input

The first line contains a number  ——The number of the testcases. And there are no more than 2 testcases with  For each testcase, the first line contains two numbers 。 The second line contains  numbers  Each of the next  lines contains the description of the query.  It is guaranteed that  At any moment.

Output

For each query of type 3, print one number which represents the answer.

Sample Input

1
10 10
56 90 33 70 91 69 41 22 77 45
1 3 9
1 1 10
3 3 8
2 5 6 74
1 1 8
3 1 9
1 2 10
1 4 9
2 8 8 69
3 3 9

Sample Output

80
122
86
在更新值变成欧拉函数相应的值的时候,效果最坏的情况是区间里每个点的值都不一样那么区间的每个点都要遍历到。然后由于第2个操作会将一段区间的值都变成相同的,所以在操作1的时候,可以不用更新每个点,只更新一下区间标记一下就可以。所以直接用线段树暴力来搞,发现是不会超时的。另外线段树的区间要注意,n最大是3*1e5;#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
typedef long long int LL;
const int maxn=1e5;
bool check[maxn*100+5];
LL prime[maxn*100+5];
LL eul[maxn*100+5];
LL sum[maxn*20+5];
LL a[maxn*20+5];
int n,m;
/*void eular(){
    eul[1] = 1;
    for (int i = 2; i<maxn*100+5; i++) eul[i] = i;
    for (int i = 2; i<maxn*100+5; i++)
        if (eul[i] == i)
            for (int j = i; j<maxn*100+5; j += i) eul[j] = eul[j] / i*(i - 1);
}
 */
void eular()
{
    memset(check,false,sizeof(check));
    eul[1]=1;
    int tot=0;
    for(int i=2;i<=maxn*100+5;i++)
    {
        if(!check[i])
        {
            prime[tot++]=i;
            eul[i]=i-1;
        }
        for(int j=0;j<tot;j++)
        {
            if(i*prime[j]>maxn*100+5) break;
            check[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                eul[i*prime[j]]=eul[i]*prime[j];
                break;
            }
            else
            {
                eul[i*prime[j]]=eul[i]*(prime[j]-1);
            }
            
        }
    }
}

void pushup(int node)
{
    sum[node]=sum[node<<1]+sum[node<<1|1];
    if(a[node<<1]==a[node<<1|1])
        a[node]=a[node<<1];
    else
        a[node]=0;
}
void pushdown(int node,int l,int r)
{
    int mid=(l+r)>>1;
    if(a[node])
    {
        sum[node<<1]=a[node]*(mid-l+1);
        sum[node<<1|1]=a[node]*(r-mid);
        a[node<<1]=a[node<<1|1]=a[node];
        //c[node<<1]=c[node<<1|1]=c[node];
        a[node]=0;
    }
}
void build(int node,int l,int r)
{
    if(l==r)
    {
        scanf("%lld",&a[node]);
        sum[node]=a[node];
        return ;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    pushup(node);
}
void update1(int node,int l,int r,int L,int R,LL tag)
{
    if(L<=l&&r<=R)
    {
        sum[node]=(LL)tag*(r-l+1);
        a[node]=tag;
        //c[node]=tag;
        return;
    }
    if(a[node]) pushdown(node,l,r);
    int mid=(l+r)>>1;
    if(L<=mid)
        update1(node<<1,l,mid,L,R,tag);
    if(R>mid)
        update1(node<<1|1,mid+1,r,L,R,tag);
    pushup(node);
}
void update2(int node,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)
    {
        if(a[node])
        {
            a[node]=eul[a[node]];
            sum[node]=a[node]*(r-l+1);
            return;
        }
        
        int mid=(l+r)>>1;
        if(L<=mid)
            update2(node<<1,l,mid,L,R);
        if(R>mid)
            update2(node<<1|1,mid+1,r,L,R);
        pushup(node);
        return ;
    }
    if(a[node]) pushdown(node,l,r);
    int mid=(l+r)>>1;
    if(L<=mid)
        update2(node<<1,l,mid,L,R);
    if(R>mid)
        update2(node<<1|1,mid+1,r,L,R);
    pushup(node);
}
LL query(int node,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)
    {
        return sum[node];
    }
    if(a[node]) pushdown(node,l,r);
    
    int mid=(l+r)>>1;
    LL ret=0;
    if(L<=mid)
        ret+=query(node<<1,l,mid,L,R);
    if(R>mid)
        ret+=query(node<<1|1,mid+1,r,L,R);
   
    return ret;
}
int main()
{
    int t;
    scanf("%d",&t);
    int x,y,z;
    LL w;
    eular();
    while(t--)
    {
        scanf("%d%d",&n,&m);
        build(1,1,n);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            if(x==1)
            {
                update2(1,1,n,y,z);
            }
            else if(x==2)
            {
                scanf("%lld",&w);
                update1(1,1,n,y,z,w);
            }
            else
            {
                printf("%lld\n",query(1,1,n,y,z));
            }
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏烂笔头

Python标准库笔记(9) — functools模块

1943
来自专栏数据之美

Python FAQ(常见问题解答)(1)

声明:转载需署名出处,严禁用于商业用途! 1、python的帮助: help(str) 可以查看str字符类的帮助信息。 2、python没有括号来表明...

2858
来自专栏飞雪无情的博客

Go语言中new和make的区别

Go语言中new和make是内建的两个函数,主要用来创建分配类型内存。在我们定义生成变量的时候,可能会觉得有点迷惑,其实他们的规则很简单,下面我们就通过一些示例...

1222
来自专栏逢魔安全实验室

UAF Writeup - pwnable.kr

0x00 UAF — pwnable.kr是一个韩国的CTF练习的网站,有很多经典的CTF题目供爱好者练习。 UAF(Use After Free)释放后重用...

3686
来自专栏玄魂工作室

Python黑帽编程2.4 流程控制

Python黑帽编程2.4 流程控制 本节要介绍的是Python编程中和流程控制有关的关键字和相关内容。 2.4.1 IF …..ELSE 先上一段代码: ...

2844
来自专栏我是攻城师

理解Java8的数据类型和运行时数据区域

Java虚拟机包含对对象的显式支持,对象要么是动态分配的类实例,要么是静态数组,对对象的引用我们可以叫做指针或者引用,一个对象可以有多个引用,对象总是通过引用的...

1523
来自专栏北京马哥教育

Python神器列传:函数神器functools模块全解析

2063
来自专栏C/C++基础

C++中的作用域与生命周期

Pascal之父Nicklaus Wirth曾经提出一个公式,展示出了程序的本质:程序=算法+数据结构。后人又给出一个公式与之遥相呼应:软件=程序+文档。这两个...

802
来自专栏小樱的经验随笔

HDU 2084 数塔(简单DP入门)

数塔 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/O...

3548
来自专栏iOS技术杂谈

Java8 Lambda表达式与Stream API (二): Stream API的使用你要知道的Java8 匿名内部类、函数式接口、lambda表达式与Stream API都在这里

你要知道的Java8 匿名内部类、函数式接口、lambda表达式与Stream API都在这里 转载请注明出处 https://cloud.tencent.co...

5426

扫码关注云+社区

领取腾讯云代金券