文章目录

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5634
线段树题，3种操作：
1 把[L,R]内的每个值val改成 φ ( v a l ) \varphi(val) φ(val)
2 把[L,R]内每个数改成x
3 求[L,R]内的和
欧拉函数求不了多少次就变成1了
主要就是剪枝：
①：如果这段区间的和等于这段区间的长度，那就说明每个数都是1了，直接退出
②：如果这个区间有lazy，又要改成欧拉值，那直接把这段lazy值改成欧拉值，然后维护sum

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=3e5+5;
const int MOD=1e9+7;
int N,Q;
const int maxN=1e7+5;
bool vis[maxN];
vector<int>prime;
int phi[maxN];
void PHI(int n)
{
	memset(vis,1,sizeof(vis));
	phi[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(vis[i])
		{
			prime.push_back(i);
			phi[i]=i-1;
		}
		for(int j=0;j<prime.size()&&(LL)i*prime[j]<=n;j++)
		{
			vis[i*prime[j]]=0;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
}
LL sum[maxn<<2],lazy[maxn<<2];
void pushup(int id)
{
	sum[id]=sum[id<<1]+sum[id<<1|1];
}
void pushdown(int id,int L,int R)
{
	if(lazy[id])
	{
		lazy[id<<1]=lazy[id];
		lazy[id<<1|1]=lazy[id];
		int mid=L+R>>1;
		sum[id<<1]=lazy[id]*(mid-L+1);
		sum[id<<1|1]=lazy[id]*(R-mid);
		lazy[id]=0;
	}
}
void Build(int id,int L,int R)
{
	lazy[id]=0;
	if(L==R)scanf("%d",&sum[id]);
	else
	{
		int mid=L+R>>1;
		Build(id<<1,L,mid);
		Build(id<<1|1,mid+1,R);
		pushup(id);
	}
}
void Update(int id,int L,int R,int qL,int qR,int cmd,LL val)
{
	if(cmd==1&&sum[id]==R-L+1)return ;//第①个剪枝 
	if(qL<=L&&qR>=R)
	{
		if(cmd==1)
		{
			if(L==R)sum[id]=phi[sum[id]];
			else
			{
				if(lazy[id])//第②个剪枝 
				{
					lazy[id]=phi[lazy[id]];
					sum[id]=lazy[id]*(R-L+1);
				}
				else
				{
					pushdown(id,L,R);
					int mid=L+R>>1;
					if(qL<=mid)Update(id<<1,L,mid,qL,qR,cmd,val);
					if(qR>=mid+1)Update(id<<1|1,mid+1,R,qL,qR,cmd,val);
					pushup(id);
				}
			}
		}
		else
		{
			sum[id]=(LL)val*(R-L+1);
			lazy[id]=val;
		}
	}
	else
	{
		pushdown(id,L,R);
		int mid=L+R>>1;
		if(qL<=mid)Update(id<<1,L,mid,qL,qR,cmd,val);
		if(qR>=mid+1)Update(id<<1|1,mid+1,R,qL,qR,cmd,val);
		pushup(id);
	}
}
LL query(int id,int L,int R,int qL,int qR)
{
	if(qL<=L&&qR>=R)return sum[id];
	else
	{
		pushdown(id,L,R);
		int mid=L+R>>1;
		LL res=0;
		if(qL<=mid)res+=query(id<<1,L,mid,qL,qR);
		if(qR>=mid+1)res+=query(id<<1|1,mid+1,R,qL,qR);
		return res;
	}
}
int main()
{
	PHI(maxN-5);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>N>>Q;
		Build(1,1,N);
		while(Q--)
		{
			int cmd,L,R,x;
			scanf("%d%d%d",&cmd,&L,&R);
			if(cmd==1)
			{
				Update(1,1,N,L,R,1,0);
			}
			else if(cmd==2)
			{
				scanf("%d",&x);
				Update(1,1,N,L,R,2,x);
			}
			else
			{
				printf("%lld\n",query(1,1,N,L,R));
			}
		}
	}
 }