Remainder Problem(Codeforces-1207F)(分块)

题目

CF

思路

分块
考虑 $f[i][j]$ 表示 ${\sum }_{x\%i=j}{a}_x$
设 $i$ 的最大值为 $B$ 那么我们对于大于 $i$ 的查询直接暴力的时间复杂度是 $O(\frac{n}{B})$
修改的时间复杂度为 $O(B)$ 于是联立等式 $\frac{n}{B}=B$ 可得 $B=\sqrt{n}$
时间复杂度为 $q\sqrt{n}$

代码

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
    int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
#define MAXN 500000
#define INF 0x3f3f3f3f
const int Block=700;
LL f[Block+5][Block+5],a[MAXN+5];
int main(){
    int q=read();while(q--){
    int opt=read(),x=read(),y=read();if(opt==1){
    for(int i=1;i<=Block;i++)f[i][x%i]+=y;a[x]+=y;}else{
    if(x<=Block)printf("%lld\n",f[x][y]);else{
    LL sum=0;for(int i=y;i<=MAXN;i+=x)sum+=a[i];printf("%lld\n",sum);}}}return 0;
}

思考

没能第一时间想到正解,但是分析出是分块做法，说明分块思想掌握不好，需要加强
注意观察时限和数据范围是否支持分块