根号算法真的是博大精深啊……明明是暴力但复杂度就是能过
这也太强了吧！！！
预处理出p<=sqrt(n)的所有情况，耗时n根n
查询：
如果p<=根n，O1查表
如果p>=根n，因为只有小于根n个数对答案有贡献，所以枚举，耗时根n
修改：
因为单点修改，直接修改1~size所有的情况，耗时根n
然后这个暴力一般的暴力就卡过了！！！！！
这也 太强 了 吧！！！！
#include#include #include #include #include #include #define maxn 160000#define sqtn 400using namespace std;inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f;}long long s[sqtn][maxn],q[maxn];int sqt;inline void update(int i,int v){ for(int j=1;j<=sqt;++j) s[j][i%j]=s[j][i%j]-q[i]+v; q[i]=v;}int main(){ int n=read(),m=read(); for(int i=1;i<=n;++i) q[i]=read(); sqt=sqrt(n); for(int i=1;i<=n;++i) for(int j=1;j<=sqt;++j) s[j][i%j]+=q[i]; for(int i=1;i<=m;++i){ char c[10];int x,y; scanf("%s%d%d",c,&x,&y); if(c[0]=='A'){ if(x<=sqt) printf("%lld\n",s[x][y]); else{ long long ans=0; for(int j=y;j<=n;j+=x) ans+=q[j]; printf("%lld\n",ans); } } else update(x,y); } return 0;}