Luogu | P3396 哈希冲突 | 根号分治

Description

众所周知，模数的 hash 会产生冲突。例如，如果模的数 p=7 ，那么 4 和 11 便冲突了。

B 君对 hash 冲突很感兴趣。他会给出一个正整数序列 $value[]$。

自然，B 君会把这些数据存进 hash 池。第 $value[k]$ 个会被存进 $k\mod p$ 这个池。这样就能造成很多冲突。

B 君会给定许多个 p 和 x ，询问在模 p 时， x 这个池内数的总和。

另外， B 君会随时更改 value[k] 。每次更改立即生效。

保证 $1<=p<n$。

Input Format

第一行，两个正整数 $n,m$ ，其中 $n$ 代表序列长度，$m$ 代表 B 君的操作次数。

第一行，$n$ 个正整数，代表初始序列。

接下来 $m$ 行，首先是一个字符 cmd ，然后是两个整数 $x,y$ 。

  • 若 cmd=A ，则询问在模 $x$ 时，$y$ 池内数的总和。
  • 若 cmd=C，则将 $value[x]$ 修改为 $y$。

Output Format

对于每个询问输出一个正整数，进行回答。

Input Sample

Sample 01

10 5
1 2 3 4 5 6 7 8 9 10
A 2 1
C 1 20
A 3 1
C 5 1
A 5 0

Output Sample

Sample 01

25
41
11

Data Range

$n,m \le 15\times 10^4$。$1 \le value[i] \le 10^3$。

Solution

根号分治。

对于小于 $\sqrt N$ 的模数，为其真正地建立池，每次修改都维护每个模数对应池中的内容，$\Theta(1)$ 回答。

对于大于 $\sqrt N$ 的模数，不实际建立池，每次修改直接修改原数列。由于询问时池中的数的个数 $\le \sqrt N$ 个，故回答的复杂度最大为 $\Theta(\sqrt N)$。

与 ZROI 2019 暑期肯竞高端峰会 A/B 班 ACM 赛 #F – Yet another vector problem (Ref. Codeforces Gym – 100739B) 类似。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

int N;
int M;

int pool[405][405];
int src[150005];

char op[3];

int main(){
    int x,y;
    Read(N);
    Read(M);
    rep(i,1,N)
        Read(src[i]);
    rep(i,1,N)
        rep(j,1,400)
            pool[j][i%j]+=src[i];
    rep(i,1,M){
        scanf("%s",op+1);
        Read(x);
        Read(y);
        if(op[1]=='A'){
            if(x<=400)
                printf("%d\n",pool[x][y]);
            else{
                int ans=0;
                for(int j=y;j<=N;j+=x)
                    ans+=src[j];
                printf("%d\n",ans);
            }
        }
        else{
            rep(j,1,400)
                pool[j][x%j]+=y-src[x];
            src[x]=y;
        }
    }
    return 0;
}