Rikka with Phi
Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Problem Description
Rikka and Yuta are interested in Phi function (which is known as Euler’s totient function).
Yuta gives Rikka an array A[1..n] of positive integers, then Yuta makes m queries.
There are three types of queries:
1 l r
Change A[i] into φ(A[i]), for all i∈[l,r].
2 l r x
Change A[i] into x, for all i∈[l,r].
3 l r
Sum up A[i], for all i∈[l,r].
Help Rikka by computing the results of queries of type 3.
Input
The first line contains a number T(T≤100) ——The number of the testcases. And there are no more than 2 testcases with n>105
For each testcase, the first line contains two numbers n,m(n≤3×105,m≤3×105)。
The second line contains n numbers A[i]
Each of the next m lines contains the description of the query.
It is guaranteed that 1≤A[i]≤107 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
Source
BestCoder Round #73 (div.1)
Recommend
hujie | We have carefully selected several similar problems for you: 6297 6296 6295 6294 6293
这又是一道与众不同的线段树，操作是区间覆盖，区间取欧拉函数，区间求和。
看起来这操作挺吓人的。但在我们AC了另外一道黑科技线段树与或之后，这题其实也不算什么了。
我们知道，一个数在不断变成它的欧拉函数若干次之后恒为一，且许多数的欧拉函数值都是相同的（数据随机）。这样的话，如果我们将修改操作进行改进，只有在当前区间在询问区间以内且当前区间中的数都相同时，我们才对这个区间进行修改，否则我们继续对其的左右儿子进行修改，尽管看起来这种思路效率极低，但如果我们仔细分析会发现，一个区间中的数被1,2" role="presentation" style="position: relative;">1,21,2操作修改若干次以后，都会变成相同的，因此这个算法的效率就有了保障，平摊下来差不多就O（nlogn）" role="presentation" style="position: relative;">O（nlogn）O（nlogn）的时间复杂度。因此问题不大。
代码如下：
#include<bits/stdc++.h>
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
#define N 300005
using namespace std;
inline long long read(){
long long ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
return ans;
}
long long phi[10000005];
bool pr[10000005];
long long prime[1000005];
int t,n,m,a[N],tot=0;
struct Node{int l,r;long long sum,num;}T[N<<2];
inline void init(){
phi[1]=1;
for(int i=2;i<=10000000;++i){
if(!pr[i])prime[++tot]=i,phi[i]=i-1;
for(int j=1;j<=tot;++j){
if(i*prime[j]>10000000)break;
pr[i*prime[j]]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
inline void pushup(int p){
T[p].sum=T[lc].sum+T[rc].sum;
T[p].num=T[lc].num==T[rc].num?T[lc].num:0;
}
inline void pushnow(int p,long long v){
T[p].num=v;
T[p].sum=v*(T[p].r-T[p].l+1);
}
inline void pushdown(int p){
if(!T[p].num)return;
pushnow(lc,T[p].num);
pushnow(rc,T[p].num);
}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r;
if(l==r){
T[p].num=T[p].sum=a[l];
return;
}
build(lc,l,mid);
build(rc,mid+1,r);
pushup(p);
}
inline void modify(int p,int ql,int qr){
if(qr<T[p].l||T[p].r<ql)return;
if(ql<=T[p].l&&T[p].r<=qr&&T[p].num){
pushnow(p,phi[T[p].num]);
return;
}
pushdown(p);
if(qr<=mid)modify(lc,ql,qr);
else if(ql>mid)modify(rc,ql,qr);
else modify(lc,ql,mid),modify(rc,mid+1,qr);
pushup(p);
}
inline void update(int p,int ql,int qr,long long v){
if(qr<T[p].l||T[p].r<ql)return;
if(ql<=T[p].l&&T[p].r<=qr){
pushnow(p,v);
return;
}
pushdown(p);
if(qr<=mid)update(lc,ql,qr,v);
else if(ql>mid)update(rc,ql,qr,v);
else update(lc,ql,mid,v),update(rc,mid+1,qr,v);
pushup(p);
}
inline long long query(int p,int ql,int qr){
if(qr<T[p].l||T[p].r<ql)return 0;
if(ql<=T[p].l&&T[p].r<=qr)return T[p].sum;
pushdown(p);
if(qr<=mid)return query(lc,ql,qr);
if(ql>mid)return query(rc,ql,qr);
return query(lc,ql,mid)+query(rc,mid+1,qr);
}
int main(){
init();
t=read();
while(t--){
memset(T,0,sizeof(T));
n=read(),m=read();
for(int i=1;i<=n;++i)a[i]=read();
build(1,1,n);
while(m--){
int op=read(),l=read(),r=read();
if(op==1)modify(1,l,r);
if(op==2){
long long v=read();
update(1,l,r,v);
}
if(op==3)printf("%lld\n",query(1,l,r));
}
}
return 0;
}