题意
给定一个序列 \(s\)，每次修改操作 \(x, y, z\)。
\(i \in [y, y + x, y + 2x, y + 3x, \ldots, y + kx]\)，\(s_i = s_i + z\)。
区间查询 \(\sum_{i = l} ^ r s_i\)。
Sol
根号分治，很明显了吧。
考虑修改操作。
- \(x > \sqrt{n}\) 直接暴力维护。
- \(x \le \sqrt{n}\) 不太好维护，考虑其他方法：
上个线段树？
不对。
考虑我们在查询的时候需要用到哪些东西：
对于 \(x > \sqrt{n}\) 的修改与原数组之和，上一个分块就能很好维护。
那 \(x \le \sqrt{n}\) 呢？
我们可以枚举 \(x\)。很难不想到当前的数组就被 \(x\) 分成了一段一段。
设 \(f_{i, j}\) 表示当前 \(x = i\)，\(y = 1 \dots j\) 的修改之和。
修改是平凡的。
查询考虑 \(O(1)\) 模拟分块。
这样这道题就做完了。
时间复杂度 \(O(n \sqrt n)\)。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <cmath>
#define ll long long
#define rg register
#define il inline
using namespace std;
/* #ifdef ONLINE_JUDGE */
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
/* #endif */
int read() {
rg int p = 0, flg = 1;
rg char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(rg int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
const int N = 2e5 + 5, M = 5005, mod = 1e9 + 7;
array <ll, N> s;
namespace ds {
int bsk, bsi;
array <array <int, M>, M> isl;
array <ll, M> bk;
int n;
il void Mod(rg ll &x) {
if (x >= mod) x -= mod;
if (x < 0) x += mod;
}
il void Mod(rg int &x) {
if (x >= mod) x -= mod;
if (x < 0) x += mod;
}
il int calc(rg int x) {
return (x - 1) / bsk + 1;
}
il int calc(rg int x, rg int y) {
return (x - 1) / y + 1;
}
il void modify(rg int x, rg int y, rg int z) {
if (x <= bsk) {
for (rg int i = y; i <= x; i++)
isl[x][i] += z, Mod(isl[x][i]);
}
else {
for (rg int i = y; i <= n; i += x)
s[i] += z, bk[calc(i)] += z;
}
}
il int query(rg int x, rg int y) {
rg ll ans = 0;
if (calc(x) == calc(y)) {
for (rg int i = x; i <= y; i++)
ans = (ans + s[i]);
}
else {
for (rg int i = x; i <= calc(x) * bsk; i++)
ans = (ans + s[i]);
for (rg int i = calc(x) + 1; i < calc(y); i++)
ans = (ans + bk[i]);
for (rg int i = (calc(y) - 1) * bsk + 1; i <= y; i++)
ans = (ans + s[i]);
}
for (rg int i = 1; i <= bsk; i++) {
rg int l1 = (x % i == 0 ? i : x % i),
l2 = (y % i == 0 ? i : y % i);
if (calc(x, i) == calc(y, i))
ans += isl[i][l2] - isl[i][l1 - 1];
else {
ans = (ans + isl[i][l2]
+ isl[i][i] - isl[i][l1 - 1]
+ 1ll * isl[i][i] * (calc(y, i) - calc(x, i) - 1) % mod);
}
}
while (ans < 0) ans += mod;
return ans % mod;
}
}
int main() {
rg int n = read(), m = read();
ds::bsk = sqrt(n) * 0.34, ds::bsi = ds::calc(n); ds::n = n;
for (rg int i = 1; i <= n; i++)
s[i] = read(), ds::bk[ds::calc(i)] += s[i], ds::Mod(ds::bk[ds::calc(i)]);
for (rg int i = 1; i <= m; i++) {
rg int op = read(), x = read(), y = read();
if (op == 1) {
rg int z = read();
ds::modify(x, y, z);
}
else write(ds::query(x, y)), puts("");
}
return 0;
}