题解 CF920F 【SUM and REPLACE】

lhm_

2019-08-08 11:40:28

Solution

可以事先打表观察每个数的约数个数,观察到如果进行替换,若干次后这个数便会被替换成1。 所以我们可以直接暴力的进行区间修改,若这个数已经到达1或2,则以后就不再修改,用并查集和树状数组进行维护。 这个方法用了[P2391 白雪皑皑](https://www.luogu.org/problem/P2391)的思想处理,用并查集标记该点已经不再用替换。 code: ```cpp #include<bits/stdc++.h> #include<cctype> #define maxn 300010 #define lowbit(x) (x&(-x)) typedef long long ll; using namespace std; ll n,m; ll fa[maxn],k,l,r; ll a[maxn],tree[maxn*4]; ll d[1000010]; template<typename T> inline void read(T &x) { x=0;char c=getchar();bool flag=false; while(!isdigit(c)){if(c=='-')flag=true;c=getchar();} while(isdigit(c)){x=x*10+(c^48);c=getchar();} if(flag)x=-x; } int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } void add(int x,ll d) { while(x<=n) { tree[x]+=d; x+=lowbit(x); } } ll query(int x) { ll sum=0; while(x) { sum+=tree[x]; x-=lowbit(x); } return sum; } int main() { for(register int i=1;i<=1000000;++i) { for(register int j=i;j<=1000000;j+=i) d[j]++;//将每个数的约数个数预处理出来,便于后面替换 } read(n); read(m); for(register int i=1;i<=n;++i) { read(a[i]); add(i,a[i]); fa[i]=i; } fa[n+1]=n+1; while(m--) { read(k); read(l); read(r); if(l>r) swap(l,r); if(k==1) { for(register int i=l;i<=r;) { add(i,(ll)d[a[i]]-a[i]); a[i]=(ll)d[a[i]]; if(a[i]<=2) fa[i]=i+1;//若这个数已经为1或2,这将其指向它下一个数 if(i==find(i)) i++; else i=fa[i];//进行跳转,忽略不再要替换的数 } } else printf("%lld\n",query(r)-query(l-1)); } return 0; } ```