题解#转载

原题+题解

CODE

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int read()
{
	char ch=getchar();
	int a=0,x=1;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') x=-x;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		a=(a<<1)+(a<<3)+(ch-'0');
		ch=getchar();
	}
	return a*x;
}
const int N=150005;
int a[N];
long long dp[400][400];  //dp[i][j]:模i为j的所有下标所对应的数的和,只需开到√n 
int n,m,x,y;
char C;
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++)  //枚举每个数 
	    for(int j=1;j<=sqrt(n);j++)  //枚举模几
		    dp[j][i%j]+=a[i]; 
	while(m--)
	{
		cin>>C;
		x=read();y=read();
		if(C=='A')   //求模x为y的和
		{
			if(x<=sqrt(n)) printf("%lld\n",dp[x][y]);  //直接输出 
			else     //若x>√n,直接暴力!              
			{
				long long ans=0;
				for(int i=y;i<=n;i+=x) ans+=a[i];  //暴力枚举加和 
				printf("%lld\n",ans);
			}
		} 
		else       //把第x个数改成y 
		{
			for(int i=1;i<=sqrt(n);i++)  //更新第x个数所涉及到的所有的池
			    dp[i][x%i]+=y-a[x]; 
			a[x]=y;
		}
	} 
	return 0;
}