【Luogu】P3396哈希冲突（根号算法）

　　题目链接

　　根号算法真的是博大精深啊……明明是暴力但复杂度就是能过

　　这也太强了吧！！！

　　预处理出p<=sqrt(n)的所有情况，耗时n根n

　　查询：

　　如果p<=根n，O1查表

　　如果p>=根n，因为只有小于根n个数对答案有贡献，所以枚举，耗时根n

　　修改：

　　因为单点修改，直接修改1~size所有的情况，耗时根n

　　然后这个暴力一般的暴力就卡过了！！！！！

　　这也  太强  了   吧！！！！

　　

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cctype>

#include<cmath>

#define maxn 160000

#define sqtn 400

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

long long s[sqtn][maxn],q[maxn];

int sqt;

inline void update(int i,int v){

    for(int j=;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=;i<=n;++i)    q[i]=read();

    sqt=sqrt(n);

    for(int i=;i<=n;++i)

        for(int j=;j<=sqt;++j)    s[j][i%j]+=q[i];

    for(int i=;i<=m;++i){

        char c[];int x,y;

        scanf("%s%d%d",c,&x,&y);

        if(c[]=='A'){

            if(x<=sqt)    printf("%lld\n",s[x][y]);

            else{

                long long ans=;

                for(int j=y;j<=n;j+=x)    ans+=q[j];

                printf("%lld\n",ans);

            }

        }

        else    update(x,y);

    }

    return ;

}