zcmimi's blog

查看原题

点击跳转

根号分治论文题

题意

给一个序列序列A,单点修改,

查询\displaystyle \sum_{i\mod p=k} A_i

暴力

查询:

for(int i=k;i<=n;i+=p)ans+=A[i];

\mathcal O(1)修改,\mathcal O(n)查询,复杂度\mathcal O(n^2)

预处理

修改A_i时预处理:

for(int p=1;p<=n;++p) //枚举模数
    ans[p][i%p]+=A[i]; //处理对应的贡献

\mathcal O(n)预处理,\mathcal O(1)查询,复杂度\mathcal O(n^2)

根号分治

只预处理p\in [1,\sqrt n]:

for(int p=1;p<=sqr;++p) //只枚举[1,√n]中的
    ans[p][i%p]+=A[i];

查询:

p<\sqrt n那么直接给出答案

p>\sqrt n时,对答案有贡献的数不超过\sqrt n

int res=0;
if(p<=sqr)
    res=ans[p][i%p];
else 
    for(int i=k;i<=n;i+=p)ans+=A[i];

修改:

void upd(int i,int v){ //将A[i]改为v
    for(int p=1;p<=sqr;++p)
        ans[p][i%p]=ans[p][i%p]-A[i]+v;
    A[i]=v;
}

完整代码:

#include<bits/stdc++.h>
const int N=150011;
int n,q,sqr,A[N],ans[400][400];
void upd(int i,int v){
    for(int p=1;p<=sqr;++p)
        ans[p][i%p]=ans[p][i%p]-A[i]+v;
    A[i]=v;
}
int main(){
    scanf("%d%d",&n,&q);
    sqr=sqrt(n);
    char opt[5];int x,y,v;
    for(int i=1;i<=n;++i)
        scanf("%d",&v),upd(i,v);
    while(q--){
        scanf("%s%d%d",opt,&x,&y);
        if(opt[0]=='A'){
            int res=0;
            if(x<=sqr)res=ans[x][y%x];
            else for(int i=y;i<=n;i+=x)res+=A[i];
            printf("%d\n",res);
        }
        else upd(x,y);
    }
}
LG 3396 哈希冲突
comment评论
Search
search