题解 P3396 【哈希冲突】
Creeper_LKF
2018-04-25 13:34:53
怎么说呢，其实是一开始复杂度推导错误，然后搞了个n^(1/3)的块出来，然后发现跑的飞快，比标解还快(792ms)（光速逃）。
后来想了想，似乎如果查询都比较大的话那么块大了没有优势，特别是用来卡暴力的大查询，反而块比较小跑的还比较优。
代码如下（前面有一些比较长的板子就忽略了，看函数名都知道干什么的，如有需要可以看R6585322）
最新：用了小号测了一把，发现n^(1/3)几乎是最快的，从pow(n,0.33)到0.3和0.35都会导致效率暴降
```
//Source Code
const int MAXN = 151111;
const int MAXB = 111;
int num[MAXN];
int block[MAXN][MAXB];
int main(){
Main_Init();
int n = read(), m = read(), block_cnt = pow(n, 0.33);
for(int i = 1; i <= n; i++){
num[i] = read();
for(int j = 1; j <= block_cnt; j++){
block[j][i % j] += num[i];
}
}
while(m --){
char cons;
while((cons = *LKF::pc ++) < 65);
int x = read(), y = read();
if(cons == 'A'){
if(x < block_cnt) write('\n', block[x][y % x]);
else {
int ans = 0;
for(int i = y; i <= n; i += x) ans += num[i];
write('\n', ans);
}
} else {
for(int i = 1; i <= block_cnt; i++){
block[i][x % i] += y - num[x];
}
num[x] = y;
}
}
Main_Init();
return 0;
}
```