分块 70tps TLE 求调

#include <bits/stdc++.h>
#define ll unsigned long long
#define str string
#define db long double
using namespace std;
constexpr ll MAXN = 1e6 + 5, mod = 571373;
ll n, q, m, qrt, a[MAXN], sum[1000], l[1000], r[1000], blg[1000];
ll tag_add[1000], tag_times[1000];
inline void pushdown(ll x) {
	if (tag_add[x] == 0 && tag_times[x] == 1)
		return;
	for (ll i = l[x]; i <= r[x]; ++i)
		((a[i] *= tag_times[x]) += tag_add[x]) %= mod;
	tag_add[x] = 0, tag_times[x] = 1;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> q >> m, qrt = sqrt(n);
	const ll sqr = qrt;
	for (ll i = 1; i <= n; ++i) {
		cin >> a[i];
		sum[(i - 1) / sqr + 1] += a[i];
		blg[i] = (i - 1) / sqr + 1;
	}
	for (ll i = 1; i <= (n - 1) / sqr + 1; ++i) {
		l[i] = r[i - 1] + 1, r[i] = min(i * sqr, n);
		tag_times[i] = 1;
	}
	while (q--) {
		ll op, x, y, z;
		cin >> op >> x >> y;
		if (op == 1) {
			cin >> z, pushdown(blg[x]);
			if (blg[x] == blg[y])
				for (ll i = x; i <= y; ++i)
					(sum[blg[i]] += a[i] * (z - 1)) %= mod, (a[i] *= z) %= mod;
			else {
				pushdown(blg[y]);
				for (ll i = x; i <= r[blg[x]]; ++i)
					(sum[blg[i]] += a[i] * (z - 1)) %= mod, (a[i] *= z) %= mod;
				for (ll i = blg[x] + 1; i < blg[y]; ++i)
					(tag_add[i] *= z) %= mod, (tag_times[i] *= z) %= mod, (sum[i] *= z) %= mod;
				for (ll i = l[blg[y]]; i <= y; ++i)
					(sum[blg[i]] += a[i] * (z - 1)) %= mod, (a[i] *= z) %= mod;
			}
		} else if (op == 2) {
			cin >> z, pushdown(blg[x]);
			if (blg[x] == blg[y])
				for (ll i = x; i <= y; ++i)
					(sum[blg[i]] += z) %= mod, (a[i] += z) %= mod;
			else {
				pushdown(blg[y]);
				for (ll i = x; i <= r[blg[x]]; ++i)
					(sum[blg[i]] += z) %= mod, (a[i] += z) %= mod;
				for (ll i = blg[x] + 1; i < blg[y]; ++i)
					(tag_add[i] += z) %= mod, (sum[i] += z * sqr) %= mod;
				for (ll i = l[blg[y]]; i <= y; ++i)
					(sum[blg[i]] += z) %= mod, (a[i] += z) %= mod;
			}
		} else {
			ll cnt = 0;
			pushdown(blg[x]);
			if (blg[x] == blg[y])
				for (ll i = x; i <= y; ++i)
					(cnt += a[i]) %= mod;
			else {
				pushdown(blg[y]);
				for (ll i = x; i <= r[blg[x]]; ++i)
					(cnt += a[i]) %= mod;
				for (ll i = blg[x] + 1; i < blg[y]; ++i)
					(cnt += sum[i]) %= mod;
				for (ll i = l[blg[y]]; i <= y; ++i)
					(cnt += a[i]) %= mod;
			}
			cout << cnt << '\n';
		}
	}
	return 0;
}