题解 CF920F 【SUM and REPLACE】

可以事先打表观察每个数的约数个数，观察到如果进行替换，若干次后这个数便会被替换成1。

所以我们可以直接暴力的进行区间修改，若这个数已经到达1或2，则以后就不再修改，用并查集和树状数组进行维护。

这个方法用了P2391 白雪皑皑的思想处理，用并查集标记该点已经不再用替换。

code：

#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;

}