题面

给出一个长度为 $n$ 的序列 $a$ ，有 $m$ 次操作，格式如下：

1 x y k 对于所有满足 $(i-1)\bmod x\le y$ $i$ 的 ，将 $a_i$ 的值加 $k$ 。

2 l r 求 $\sum_{i=l}^r a_i$ 。

数组下标从 1 开始。

$n,m\leq2\times10^5$ 。

题解

分块维护差分数组。特别地，对于所有小于块长的 $x$ ，直接维护它的和还有它的前缀和（代码里面把所有小的 $x$ 的前缀和合并到一个数组里了）。注意取块编号的函数定义域一定要在 $[1,n]$ ！

代码

const int N = 5e5 + 5, sqrtN = 510;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	ll n, m, L;
	ll a[N];

	ll getB(ll x) {return (x >= 1 && x <= n)? (x - 1) / L + 1: 0;}
	ll bL[sqrtN << 1], bR[sqrtN << 1];
	ll sum[sqrtN << 1], ssum[sqrtN << 1];
	ll t[N];
	void add (ll l, ll r, ll k) {
		t[l] += k;
		sum[getB(l)] += k;
		ssum[getB(l)] += (bR[getB(l)] - l + 1) * k;
		if (r == n) return;
		t[r + 1] -= k;
		sum[getB(r + 1)] -= k;
		ssum[getB(r + 1)] -= (bR[getB(r + 1)] - r) * k;
	}
	ll ask (ll l, ll r) {
		ll ret = 0;
		for (ll i = 1; i < getB(l); i++) ret += sum[i] * (r - l + 1);

		for (ll i = bL[getB(l)]; i < l; i++) ret += t[i] * (r - l + 1);
		if (getB(l) == getB(r)) {
			for(ll i = l; i <= r; i++) ret += t[i] * (r - i + 1);
			return ret;
		}
		for (ll i = l; i <= bR[getB(l)]; i++) ret += t[i] * (r - i + 1);
		for (ll i = getB(l) + 1; i < getB(r); i++) ret += ssum[i] + sum[i] * (r - bL[i + 1] + 1);
		for (ll i = bL[getB(r)]; i <= r; i++) ret += t[i] * (r - i + 1);
		return ret;
	}

	ll d[sqrtN], ds[N * 2];
	ll askd (ll x, ll r) {
		if (r == -1) return 0;
		return (r / x) * d[x] + ds[x * 1000 + r % x];
	}

	int main () {
		n = Read(), m = Read();
		L = sqrt(n) / 2;
		for (ll i = 1; i <= n; i++) 
			a[i] = Read() + a[i - 1];
		for (ll i = 1; i <= n; i++) {
			if (!bL[getB(i)]) bL[getB(i)] = i;
			bR[getB(i)] = i;
		}
		for (; m--; ) {
			int op = Read();
			if (op == 1) {
				ll x = Read(), y = Read();ll k = Read();
				y = min (y, x - 1);
				if (x <= L) {
					d[x] += k * (y + 1);
					ll sum = 0, posB = x * 1000;
					for(ll i = 0; i <= y; i++) {
						sum += k;
						ds[posB + i] += sum;
					}
					for(ll i = y + 1; i < x; i++) ds[posB + i] += sum;
				} else {
					for (ll l = 1; l <= n; l += x) add(l, l + y, k);
				}
			} else {
				ll l = Read(), r = Read();
				ll ans = a[r] - a[l - 1]; 
				for (ll i = 1; i <= L; i++) ans += askd(i, r - 1) - askd(i, l - 2); 
				ans += ask(l, r);
				printf ("%lld\n", ans);
			}
		}
		return 0;
	}
}

int main () {
	freopen("scarlet.in", "r", stdin);
	freopen("scarlet.out", "w", stdout);
	Main::main();
	return 0;
}