题解 P3396 【哈希冲突】

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;
}