P5309 [Ynoi2011] 初始化
考虑暴力，模拟题意，时间复杂度竟是\(O(\frac{n^2}{x})\)，那么对于\(x \ge \sqrt{n}\)的修改就可以暴力了，这不是根号分治吗。
再去考虑\(x < \sqrt{n}\)的修改，那么不同的\(x\)最多只有\(\sqrt{n}\)个，维护一个余数的前缀和和一个后缀和即可，对询问\(l,r\)按\(x\)分块，就可以算贡献了，总时间复杂度为\(O(n\sqrt{n})\)。
Code
#include<cstdio>
#include<iostream>
#include<cmath>
#define IN inline
#define RE register
#define LL long long
using namespace std;
const int N = 2e5 + 5, M = 800, P = 1e9 + 7;
int bl[N], g[M][M], f[M][M], a[N], vis[M], B, st[M], ed[M], n, m;
IN int read() {
LL res = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar());
for (; isdigit(ch); ch = getchar()) res = ((res << 3) + (res << 1) + (ch ^ 48)) % P;
return res;
}
IN int Add(int x, int y){return x + y >= P ? x + y - P : x + y;}
IN int query(int l, int r) {
int res = 0;
for (RE int i = 1; i < B; i++) {
int q = (l + i - 1) / i, p = (r + i - 1) / i;
int L = l - (q - 1) * i, R = r - (p - 1) * i;
(p - q > 1) && (res = Add(res, (LL)(p - q - 1) * f[i][i] % P));
(p == q) && (res = Add(res, Add(f[i][R] - f[i][L - 1], P)));
(p != q) && (res = Add(res, Add(g[i][L], f[i][R])));
}
int x = bl[l], y = bl[r];
if (x == y) {
for (RE int i = l; i <= r; i++) res = Add(res, a[i]);
return res;
}
for (RE int i = l; i <= ed[x]; i++) res = Add(res, a[i]);
for (RE int i = st[y]; i <= r; i++) res = Add(res, a[i]);
for (RE int i = x + 1; i < y; i++) res = Add(res, vis[i]);
return res;
}
int main() {
n = read(), m = read(), B = sqrt(n);
if (B > 200) B -= 200;
for (RE int i = 1; i <= n; i++) a[i] = read();
int len = n / B;
for (RE int i = 1; i <= len; i++) st[i] = ed[i - 1] + 1, ed[i] = i * B;
ed[len] = n;
for (RE int i = 1; i <= len; i++)
for (RE int j = st[i]; j <= ed[i]; j++) bl[j] = i, vis[i] = Add(vis[i], a[j]);
for (; m; m--) {
int opt = read(), x = read(), y = read(), z;
if (opt == 1) {
z = read();
if (x < B) {
for (RE int i = y; i <= x; i++) f[x][i] = Add(f[x][i], z);
for (RE int i = 1; i <= y; i++) g[x][i] = Add(g[x][i], z);
}
else for (RE int i = y; i <= n; i += x) a[i] = Add(a[i], z), vis[bl[i]] = Add(vis[bl[i]], z);
}
else printf("%d\n",query(x, y));
}
}