洛谷3396：哈希冲突——题解-白红宇

洛谷3396：哈希冲突——题解

阅读量：7039 次

发布时间：2019-06-28

本文共 1688 字，大约阅读时间需要 5 分钟。

众所周知，模数的hash会产生冲突。例如，如果模的数p=7，那么4和11便冲突了。

B君对hash冲突很感兴趣。他会给出一个正整数序列value[]。

自然，B君会把这些数据存进hash池。第value[k]会被存进(k%p)这个池。这样就能造成很多冲突。

B君会给定许多个p和x，询问在模p时，x这个池内数的总和。

另外，B君会随时更改value[k]。每次更改立即生效。

保证

哈希是骗你的。参考洛谷题解。

正解做法十分的妙，是一道参考集训队论文《根号算法——不只是分块》出的论文题。

首先暴力肯定是没有前途的O(n)查询。

预处理ans[p][x]表示p为模数时第x个池数的总和。

也是没有前途的O(n^2)预处理。

所以如果没有看过论文的可能就不会往正解想（比如本蒟蒻），看到算法标签为分块也会不知所以然。

正解：预处理ans[p][x]时p最大到sqrt(n)。

至于大于sqrt(n)的p我们可以暴力（最多只会有sqrt(n)个数会被你查到）。

修改操作很傻就不说了。

总之我们做完了。

（然而这真的不是分块emmm……这只是根号算法……洛谷欺骗我感情。）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int N=150001;const int SQRTN=401;const int lim=1000;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}char ch[10];int n,m,s,a[N];int ans[SQRTN][lim+10];inline void init(){ for(int p=1;p<=s;p++){ for(int i=1;i<=n;i++){ ans[p][i%p]+=a[i]; } } return;}inline int query(int p,int x){ if(x>lim)return 0; if(p<=s)return ans[p][x]; int sum=0; for(int i=x;i<=n;i+=p)sum+=a[i]; return sum;}inline void modify(int x,int y){ for(int p=1;p<=s;p++){ ans[p][x%p]-=a[x]; ans[p][x%p]+=y; } a[x]=y;}int main(){ n=read();m=read();s=sqrt(n); for(int i=1;i<=n;i++)a[i]=read(); init(); for(int i=1;i<=m;i++){ cin>>ch; int x=read(),y=read(); if(ch[0]=='A')printf("%d\n",query(x,y)); else modify(x,y); } return 0;}