哈希冲突 题解 根号科技

· · 题解

题目传送门

题意

Sol

2014 年集训队论文 《根号算法——不只是分块》 ——王悦同 例一加强版。

原题是没有修改操作的，但单点修改没有提高本题难度。（

既然都根号算法了那就往根号上想

若 x \ge \sqrt n 则直接暴力跳就行了，此时复杂度小于 O(\sqrt n)。

考虑预处理 x < \sqrt n 的情况。

考虑定义 f_{i,j} 为 x=i，y=j 时的答案。（此题问法保证了 y\le x）

考虑每个点对 f 的贡献。

显然 a_x 仅对 f_{i,x%i} 有 a_x 的贡献，所以每个点仅有 O(\sqrt n) 的复杂度。

更新与其相同。

总复杂度 O((n+m)\sqrt n)。

\text{Code}

// wish to get better qwq

#include<bits/stdc++.h>
#define re register int
#define pb push_back

using namespace std;
typedef long long ll;

template <typename T> void rd(T &x){
    ll fl=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    x*=fl;
}
void wr(ll x){
    if(x<0) x=-x,putchar('-');
    if(x<10) putchar(x+'0');
    if(x>9) wr(x/10),putchar(x%10+'0');
}

char op;
inline void getop(){
    op=getchar();
    while(op!='A'&&op!='C') op=getchar();
}

// ---------- IO ---------- //

const int N=2e5+5,SQ=505;
ll n,m,v[N],len,qaq,qwq;
ll f[N][SQ];    // 当时傻了开大了

inline void modify(ll x,ll y){
    for(re i=1;i<=len;i++) f[i][x%i]+=y-v[x];
    v[x]=y;
}

inline ll query(ll x,ll y){
    if(x<=len) return f[x][y%x];
    ll sum=0;
    for(re i=y%x;i<=n;i+=x) sum+=v[i];
    return sum;
}

// ---------- Sqrt & Operations ---------- //

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    rd(n);rd(m);len=(int)sqrt(n);
    for(re i=1;i<=n;i++){
        int x;rd(x);modify(i,x);
    }
    while(m--){
        getop();rd(qaq);rd(qwq);
        if(op=='A') wr(query(qaq,qwq)),puts("");
        else modify(qaq,qwq);
    }
    return 0;
}

// ---------- Main ---------- //

说完这题，我们再来考虑一下论文题。

$x < \sqrt n$ 时，还是需开一个 $f_{i,j}$ 表示 $x=i$，$y=j$ 的答案。 对于每个 $x$，从后往前更新即可。