题意
给定一个序列，你需要维护下面两种操作：
- 将所有 \(i mod k \in [l, r]\) 的 \(a_i\) 加上 \(x\)
- 求 \(\sum_{i = l} ^ r a_i\)
Sol
考场代码挂成 \(35\) 了，数组全开两倍就直接过了/cf
初始化加强版，把单修改成了区修。
类似初始化，考虑对 \(k\) 根号分治。
不难发现当 \(k \le \sqrt n\) 时，直接套用初始化的做法即可。
考虑 \(k \ge \sqrt n\)，发现当前最多支持维护一个差分数组。
接下来的思路就一目了然了，考虑每 \(\sqrt n\) 个操作就重构一遍这个差分数组，把这个数组加到原数组上。
与当前操作不超过 \(\sqrt n\) 的操作就直接暴力做，和查询 \(\le \sqrt n\) 一样的模拟分块即可。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <tuple>
#include <vector>
#define int long long
#define tupl tuple <int, int, int, int>
using namespace std;
int read() {
int p = 0, flg = 1;
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(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
const int N = 4e5 + 5, blk = 327;
array <int, 4 * blk + 5> bk;
array <int, N> s, h;
int calc(int x) {
return (x - 1) / blk + 1;
}
int calc(int x, int y) {
return x / y;
}
array <array <int, 4 * blk + 5>, 4 * blk + 5> cur;
vector <tupl> isl;
void modify(int x, int l, int r, int k, int n) {
if (x > blk) {
for (int i = l; i <= n; i += x)
h[i] += k, h[i + r - l + 1] -= k;
isl.push_back(make_tuple(x, l, r, k));
}
else {
for (int i = l; i <= r; i++)
cur[x][i] += (i - l + 1) * k;
for (int i = r + 1; i < x; i++)
cur[x][i] += (r - l + 1) * k;
}
}
int query(int l, int r, int n) {
int ans = 0;
if (calc(l) == calc(r))
for (int i = l; i <= r; i++)
ans += s[i];
else {
for (int i = l; i <= calc(l) * blk; i++)
ans += s[i];
for (int i = (calc(r) - 1) * blk + 1; i <= r; i++)
ans += s[i];
for (int i = calc(l) + 1; i <= calc(r) - 1; i++)
ans += bk[i];
}
for (int i = 1; i <= blk; i++) {
int l1 = l % i, l2 = r % i;
if (calc(l, i) == calc(r, i))
ans += cur[i][l2] - (!l1 ? 0 : cur[i][l1 - 1]);
else {
ans = (ans + cur[i][l2]
+ cur[i][i - 1] - (!l1 ? 0 : cur[i][l1 - 1])
+ cur[i][i - 1] * (calc(r, i) - calc(l, i) - 1));
}
}
return ans;
}
int getsum(int l, int r, int k) { return (r >= l) * (r - l + 1) * k; }
signed main() {
freopen("sorrow.in", "r", stdin);
freopen("sorrow.out", "w", stdout);
int n = read(), m = read();
for (int i = 1; i <= n; i++)
s[i] = read(), bk[calc(i)] += s[i];
int cnt = 0;
for (int i = 1; i <= m; i++) {
int op = read();
if (op == 1) {
int x = read(), l = read(), r = read(), k = read();
modify(x, l, r, k, n);
}
else {
int _l = read(), _r = read();
int ans = 0;
for (auto &[x, l, r, k] : isl) {
int l1 = _l % x, l2 = _r % x;
if (calc(_l, x) == calc(_r, x))
ans += getsum(max(l, l1), min(r, l2), k);
else {
ans += getsum(max(l, l1), r, k);
ans += getsum(l, min(r, l2), k);
int tp = ((calc(_r, x) - calc(_l, x) - 1) > 0);
ans += tp * (calc(_r, x) - calc(_l, x) - 1) * (r - l + 1) * k;
}
}
write(ans + query(_l, _r, n)), puts("");
}
if (i % blk == 0) {
for (int i = 1; i <= n; i++)
h[i] += h[i - 1], s[i] += h[i], bk[calc(i)] += h[i];
h.fill(0);
isl.clear();
}
}
return 0;
}