E. Remainder Problem 分块

两个操作

1对x位置的a[x]+y

2对所有i=y（mod x）求a[i]的和

我们肯定不能n^2 跑，稳超时，但是我们可以这样分块考虑。

为什么n^2不行？因为在x比较小的时候，这个求和操作次数太多了。但是x比较大的时候，这个对时间并没有什么影响

所有我们考虑分块。

用一个dp[i][j]表示(1-5e5的长度分成了长度为x的块,且块内偏移为j)的所有位置的和。

那么操作1，对a[pos]+=x后，需要对所有块长1到sqrt(len)的pos所处的块内偏移位置进行维护，以保证在询问块长1-sqrt(len)的时候，我们都能o(1)回答

如果块长大于sqrt(len)后，我们数组已经开不下，并且维护的时间将超出O（sqrt(5e5)），我们考虑直接暴力

因为此时块长大于sqrt(len)后，我们暴力加和的次数最大也就sqrt(5e5)，并且随着块长数越大，次数也就越少

通过这个两种情况，我们就把时间复杂度下降到了o(sqrt(5e5))=700*5e5次查询，4秒也是可以接受的。（其实我感觉是接受不了的，谁叫cf跑的快）。。。

#include<bits/stdc++.h>

using namespace std;

#define LL long long

const int maxn = 5e5+;

LL dp[][];

LL a[maxn];

int main(){

  int t,op;

  LL x,y;

  scanf("%d",&t);

  while(t--){

    scanf("%d",&op);

    if(op==){

        scanf("%lld%lld",&x,&y);

        a[x]+=y;

        for(int i=;i<;i++){

            dp[i][x%i]+=y;

        }

    }else {

        scanf("%lld%lld",&x,&y);

        if(x<){

          printf("%lld\n",dp[x][y]);

        }else {

         LL ans=;

          for(int i=y;i<=5e5;i+=x){

             ans+=a[i];

          }

          printf("%lld\n",ans);

        }

    }

  }

  return ;

}

巴特西

E. Remainder Problem 分块

最新文章

热门文章