根号分治刷题记录

根号分治就是，如果m次询问，每次询问规模都是<=n；然后就分出大于(sqrt(n))的部分和小于(sqrt(n))的部分，其中小于(sqrt(n))的部分往往可以O（n）预处理，大于(sqrt(n))的部分暴力计算每次只需要花费O（(sqrt(n))），总之就是暴力美学啦。。。。

洛谷P3396哈希冲突

注意到(p<sqrt(n))的部分可以预处理，然后修改也可以O（(sqrt(n))）修改，于是。。。

#include <bits/stdc++.h>
#define N 150010
#define SN 400
#define f(c,a,b) for(int c=a; c<=b; c++)

using namespace std;
int v[N];
int n, m, c;
int a[SN][SN];

void pre(){ f(i,1,c) f(j,1,n) a[i][j%i] += v[j]; }
void change(int p, int x){ f(i,1,c) a[i][p%i] += x; }

int main(){
    //freopen("owo.in","r",stdin);
    cin >> n >> m;
    c = (int)sqrt(n);
    f(i,1,n) scanf("%d", &v[i]);
    pre();
    int x, y;
    char pd[10];
    f(i,1,m){
        scanf("%s%d%d", &pd, &x, &y);
        if(pd[0] == 'A'){  //ask
            int ans = 0;
            if(x >= c) for (int j=y; j<=n; j+=x) ans += v[j];
            else ans = a[x][y];
            printf("%d
", ans);
        }else{ //change
            change(x, y-v[x]);
            v[x] = y;
        }
    }
    return 0;
}