题解 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; } ```