哈希冲突 题解 根号科技

### [题目传送门](https://www.luogu.com.cn/problem/P3396) ## 题意 - 给定一个序列，支持单点修改和跳点求和（即 $y+kx(k\in N)$ 的位置上的和） ## 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}$ ```cpp // 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$，$y$，问 $y+kx(k \in N)$ 的位置上的和。 - 不保证 $y\le x$ $x \ge \sqrt n$ 时仍暴力跑。 $x < \sqrt n$ 时，还是需开一个 $f_{i,j}$ 表示 $x=i$，$y=j$ 的答案。 对于每个 $x$，从后往前更新即可。