洛谷P3396 哈希冲突（分块）

传送门

题解在此，讲的蛮清楚的->这里

我就贴个代码

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 char sr[<<],z[];int C=-,Z;

 inline void Ot(){fwrite(sr,,C+,stdout),C=-;}

 inline void print(int x){

     if(C><<)Ot();if(x<)sr[++C]=,x=-x;

     while(z[++Z]=x%+,x/=);

     while(sr[++C]=z[Z],--Z);sr[++C]='\n';

 }

 inline char getop(){

     char ch;

     while((ch=getc())!='A'&&ch!='C');

     return ch;

 }

 const int N=,M=;

 int ans[M][M],v[N],s,n,m;

 int main(){

 //    freopen("testdata.in","r",stdin);

     n=read(),m=read(),s=pow(n,0.3333);

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

         v[i]=read();

         for(int j=;j<=s;++j)

         ans[j][i%j]+=v[i];

     }

     while(m--){

         char op=getop();int x=read(),y=read();

         switch(op){

             case 'A':{

                 if(x<=s) print(ans[x][y%x]);

                 else{

                     int res=;

                     for(int i=y;i<=n;i+=x) res+=v[i];

                     print(res);

                 }

                 break;

             }

             case 'C':{

                 for(int i=;i<=s;++i) ans[i][x%i]+=y-v[x];

                 v[x]=y;

                 break;

             }

         }

     }

     Ot();

     return ;

 }