[P3396] 哈希冲突

Link:

P3396 传送门

Solution:

其实就是要求$sum a[k*x+y]$

按$x$分类处理：

1、如果$x>sqrt(n)$，那么$k<sqrt(n)$直接暴力

2、如果$x<sqrt(n)$，$O(n*sqrt(n))$预处理，$O(sqrt(n))$修改

这是一道论文题，体现的就是对数据分类的思想

此题中步长和项数是乘积关系，因此分类处理步长大和项数多的情况

Code:

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second
#define pb push_back
typedef double db;
typedef long long ll;
typedef pair<int,int> P;
const int MAXN=5e5+10;
char op[5];int x,y;
int n,q,dat[MAXN];ll pre[1000][1000];

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&dat[i]);
    int block=sqrt(n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=block;j++)
            pre[j][i%j]+=dat[i];
    
    while(q--)
    {
        scanf("%s%d%d",op,&x,&y);
        if(op[0]=='C')
        {
            for(int i=1;i<=block;i++)
                pre[i][x%i]-=dat[x],pre[i][x%i]+=y;
            dat[x]=y;
        }
        else
        {
            if(x<=block) 
                printf("%lld
",pre[x][y]);
            else 
            {
                ll res=0;
                for(int i=y;i<=n;i+=x) res+=dat[i];
                printf("%lld
",res);
            }
        }        
    }
    return 0;
}