题意：bc round 73 div1 D 中文题面
分析：注意到10^7之内的数最多phi O(log(n))次就会变成1，
因此可以考虑把一段相同的不为1的数缩成一个点，用平衡树来维护。
每次求phi的时候就在平衡树上取出这个区间然后暴力求phi，如果一段数变成了1，
就在平衡树里面删掉它，最后统计答案的时候只要把区间中被删去的1加回答案即可，
时间复杂度O((n + m)logn)
注：平衡树，写起来麻烦（然后其实我也不会写）
但是题解当中说把一段相同的数缩成一个点，就很好
所以用线段树，节点维护区间和以及（当这个区间元素都相同时）维护这个元素
然后操作2和操作3就是普通的线段树应用，区间更新以及区间求和
然后操作1，由于我维护了一整段相同元素的区间，所以更新时，
只要按照区间更新，区间在更新范围内，且节点所管辖区间的元素全部相同的时候，直接修改节点
区间更新就好了，这样的话，时间复杂度不是很高
由于单个元素的范围是1e7，所以先筛一遍欧拉函数
#include <cstdio> #include <iostream> #include <cstring> using namespace std; typedef long long LL; const int N = 1e7; const int maxn=3e5+5; const LL mod = 1e9+7; int phi[N+50],n,m,T; int o[maxn<<2],mark[maxn<<2]; LL sum[maxn<<2]; void pushup(int rt) { sum[rt]=sum[rt*2]+sum[rt*2+1]; if(o[rt*2]==o[rt*2+1]&&o[rt*2]) o[rt]=o[rt*2]; else o[rt]=0; } void pushdown(int rt,int l,int r) { if(mark[rt]) { int mid=(l+r)>>1; sum[rt*2]=1ll*(LL)(mid-l+1)*(LL)(mark[rt]); sum[rt*2+1]=1ll*(LL)(r-mid)*(LL)(mark[rt]); o[rt*2]=o[rt*2+1]=mark[rt]; mark[rt*2]=mark[rt*2+1]=mark[rt]; mark[rt]=0; } } void build(int rt,int l,int r) { if(l==r) { scanf("%d",&o[rt]); sum[rt]=o[rt]; return ; } int mid=(l+r)>>1; build(rt*2,l,mid); build(rt*2+1,mid+1,r); pushup(rt); } void op1(int rt,int l,int r,int x,int y) { if(x<=l&&r<=y&&o[rt]) { int tmp=phi[o[rt]]; o[rt]=mark[rt]=tmp; sum[rt]=1ll*(LL)(r-l+1)*(LL)(tmp); return; } pushdown(rt,l,r); int mid=(l+r)>>1; if(x<=mid)op1(rt*2,l,mid,x,y); if(y>mid)op1(rt*2+1,mid+1,r,x,y); pushup(rt); } int t; void op2(int rt,int l,int r,int x,int y) { if(x<=l&&r<=y) { o[rt]=mark[rt]=t; sum[rt]=1ll*(LL)(r-l+1)*(LL)(t); return; } pushdown(rt,l,r); int mid=(l+r)>>1; if(x<=mid)op2(rt*2,l,mid,x,y); if(y>mid)op2(rt*2+1,mid+1,r,x,y); pushup(rt); } LL op3(int rt,int l,int r,int x,int y) { if(x<=l&&r<=y) return sum[rt]; pushdown(rt,l,r); int mid=(l+r)>>1; LL ans=0; if(x<=mid)ans+=op3(rt*2,l,mid,x,y); if(y>mid)ans+=op3(rt*2+1,mid+1,r,x,y); return ans; } int main() { phi[1]=1; for(int i=2; i<=N; ++i) { if(!phi[i]) { for(int j=i; j<=N; j+=i) { if(!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1); } } } scanf("%d",&T); while(T--) { memset(o,0,sizeof(o)); memset(mark,0,sizeof(mark)); scanf("%d%d",&n,&m); build(1,1,n); while(m--) { int c,l,r; scanf("%d%d%d",&c,&l,&r); if(c==2)scanf("%d",&t); if(c==1)op1(1,1,n,l,r); else if(c==2)op2(1,1,n,l,r); else printf("%I64d\n",op3(1,1,n,l,r)); } } return 0; }
原文：http://www.cnblogs.com/shuguangzw/p/5221615.html
