题目描述
输出格式
For each query of type 3, print one number which represents the answer.
样例
样例输入
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
样例输出
80
122
86
分析
因为 (phi[i]) 一定是小于等于 (i) 的
所以对于 (1) 操作，在进行若干次后整个区间就会变成 (1)
因此当整个区间内的数字都相同的时候，我们直接给整个区间打标记
否则暴力递归左右儿子
对于 (2) 操作，我们直接打一个区间赋值的标记就行了
时间复杂度：跑得挺快
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<map>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5,maxm=1e7+5;
int t,n,m,a[maxn],mmax;
bool not_pri[maxm];
int pri[maxm],phi[maxm];
void xxs(){
not_pri[0]=not_pri[1]=1;
phi[1]=1;
for(rg int i=2;i<=mmax;i++){
if(!not_pri[i]){
pri[++pri[0]]=i;
phi[i]=i-1;
}
for(rg int j=1;j<=pri[0] && i*pri[j]<=mmax;j++){
not_pri[i*pri[j]]=1;
if(i%pri[j]==0){
phi[i*pri[j]]=phi[i]*pri[j];
break;
} else {
phi[i*pri[j]]=phi[i]*phi[pri[j]];
}
}
}
}
struct trr{
int l,r,val,num,laz,siz;
long long sum;
}tr[maxn<<2];
void push_up(rg int da){
tr[da].sum=tr[da<<1].sum+tr[da<<1|1].sum;
tr[da].num=(tr[da<<1].num==tr[da<<1|1].num)?tr[da<<1].num:0;
}
void updat(rg int da,rg int val){
tr[da].laz=val;
tr[da].val=val;
tr[da].num=val;
tr[da].sum=1LL*val*tr[da].siz;
}
void push_down(rg int da){
if(tr[da].laz==-1) return;
updat(da<<1,tr[da].laz);
updat(da<<1|1,tr[da].laz);
tr[da].laz=-1;
}
void build(rg int da,rg int l,rg int r){
tr[da].l=l,tr[da].r=r,tr[da].laz=-1,tr[da].siz=r-l+1;
if(tr[da].l==tr[da].r){
tr[da].sum=tr[da].val=tr[da].num=a[l];
return;
}
rg int mids=(tr[da].l+tr[da].r)>>1;
if(l<=mids) build(da<<1,l,mids);
if(r>mids) build(da<<1|1,mids+1,r);
push_up(da);
}
void xg1(rg int da,rg int l,rg int r){
if(tr[da].l>=l && tr[da].r<=r && tr[da].num){
updat(da,phi[tr[da].num]);
return;
}
push_down(da);
rg int mids=(tr[da].l+tr[da].r)>>1;
if(l<=mids) xg1(da<<1,l,r);
if(r>mids) xg1(da<<1|1,l,r);
push_up(da);
}
void xg2(rg int da,rg int l,rg int r,rg int val){
if(tr[da].l>=l && tr[da].r<=r){
updat(da,val);
return;
}
push_down(da);
rg int mids=(tr[da].l+tr[da].r)>>1;
if(l<=mids) xg2(da<<1,l,r,val);
if(r>mids) xg2(da<<1|1,l,r,val);
push_up(da);
}
long long cxsum(rg int da,rg int l,rg int r){
if(tr[da].l>=l && tr[da].r<=r) return tr[da].sum;
push_down(da);
rg int mids=(tr[da].l+tr[da].r)>>1;
rg long long nans=0;
if(l<=mids) nans+=cxsum(da<<1,l,r);
if(r>mids) nans+=cxsum(da<<1|1,l,r);
return nans;
}
int main(){
mmax=1e7;
xxs();
t=read();
while(t--){
n=read(),m=read();
for(rg int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
rg int aa,bb,cc,dd;
for(rg int i=1;i<=m;i++){
aa=read(),bb=read(),cc=read();
if(aa==1){
xg1(1,bb,cc);
} else if(aa==2){
dd=read();
xg2(1,bb,cc,dd);
} else {
printf("%lld
",cxsum(1,bb,cc));
}
}
}
return 0;
}