洛谷3396 哈希冲突

Luogu

分析

根号分治。

设$ans[i][j]$表示模$i$意义下第$j$个池的和。

显然可以$O(n^2)$预处理,$O(1)$查询,然而时空都会炸。

可以只预处理到$\sqrt{n}$,这样子预处理就降到了$O(n\sqrt{n})$。

对于查询,如果$x\leq\sqrt{n}$,显然可以$O(1)$回答。

如果$x>\sqrt{n}$,那么暴力统计即可。此时最多只有$\left\lfloor\frac{n}{x}\right\rfloor$个数,所以这部分是$O(\sqrt{n})$的。

修改时只要修改$\sqrt{n}$范围内的ans就行了。

总时间复杂度大概是$O((n+m)\sqrt{n})$。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=150000+10;
const int MAXM=390+10;

int ans[MAXM][MAXM];
int val[MAXN];

int main() {
    int n=read(),m=read();
    for (re int i=1;i<=n;++i) val[i]=read();
    int size=floor(sqrt(n));
    for (re int i=1;i<=n;++i)
        for (re int p=1;p<=size;++p)
            ans[p][i%p]+=val[i];
    while (m--) {
        char op=getchar();
        while (!isalpha(op)) op=getchar();
        int x=read(),y=read();
        if (op=='A') {
            if (x<=size) printf("%d\n",ans[x][y]);
            else {
                int sum=0;
                for (re int i=y;i<=n;i+=x)
                    sum+=val[i];
                printf("%d\n",sum);
            }
        }
        else if (op=='C') {
            for (re int p=1;p<=size;++p)
                ans[p][x%p]+=y-val[x];
            val[x]=y;
        }
    }
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 37 PM

发表评论