[LUOGU 哈希冲突] 巧妙根号算法

本文主要是介绍[LUOGU 哈希冲突] 巧妙根号算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

题目链接：[LUOGU 哈希冲突]
题解：
一看到是rxz大佬的题目，，就上去做了做，但是，，为什么挂出来分块的标签，但是呢，，，，跟分块，，一点关系都没有啊！！！！!
不瞎扯了，，，进入正题，，，
先解释一下题面：
就是给你一串数，对于标号进行操作，标号取模得x的，把他给的数的劝权值进行取和。
就是$n\sqrt{n}$进行预处理，之后的可以$O(1)$处理$\sqrt{n}$之前的答案，然后就$n\sqrt{n}$处理之后的答案就好了，这样的话就是$n\sqrt{n}$了。
（这都是什么解法啊，，，，竟然还写分块的标签，，，，）

代码：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch<='9'&&ch>='0')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int sea=1e5+5e4+7;
const int pool=500;
int n,m,block,a[sea],ans[sea][pool];
int main()
{n=read();m=read(); block=pow(n,0.33);for(int i=1;i<=n;i++) {a[i]=read();for(int j=1;j<=block;j++) ans[j][i%j]+=a[i];}while(m--){char ch; cin>>ch;int x=read(),y=read();if(ch=='A'){if(x<=block) printf("%d\n",ans[x][y]);else{int sum=0;for(int i=y;i<=n;i+=x) sum+=a[i];printf("%d\n",sum);}}else{for(int i=1;i<=block;i++) ans[i][x%i]-=(a[x]-y);a[x]=y; } }return 0; 
}

Continue……

这篇关于[LUOGU 哈希冲突] 巧妙根号算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---