HDU 5634 Rikka with Phi (线段树)
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 9Sample 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;
}