问题锁定在 insert2 和更新乘法的标记

#include <bits/stdc++.h>

using namespace std;

const int p = 571373, N = 1e5 + 50;

int n, q, _;
long long f[N * 4], v1[N * 4], v2[N * 4], a[N];

void buildtree(int k, int l, int r) {
	v1[k] = 0;
	v2[k] = 1;
	if (l == r) {
		f[k] = a[l];
		return;
	}
	int m = (l + r) >> 1;
	buildtree(k + k, l, m);
	buildtree(k + k + 1, m + 1, r);
	f[k] = (f[k + k] + f[k + k + 1]) % p;
}

void insert1(int k, int l, int r, int x, int y, long long z) {
	if (l == x && r == y) {
		v1[k] = (v1[k] + z) % p;
		return;
	}
	if (v1[k]) 
		v1[k + k] = (v1[k + k] + v1[k]) % p, v1[k + k + 1] = (v1[k + k + 1] + v1[k]) % p, v1[k] = 0;
	if (v2[k] > 1) 
		v2[k + k] = (v2[k + k] * v2[k]) % p, v2[k + k + 1] = (v2[k + k + 1] * v2[k]) % p, v2[k] = 1;	
	int m = (l + r) >> 1;
	if (y <= m) insert1(k + k, l, m, x, y, z);
	else if (x > m) insert1(k + k + 1, m + 1, r, x, y, z);
	else insert1(k + k, l, m, x, m, z), insert1(k + k + 1, m + 1, r, m + 1, y, z);
	f[k] = (((f[k + k] * v2[k + k]) % p + v1[k + k] * v2[k + k] * (m - l + 1)) % p + ((f[k + k + 1] * v2[k + k + 1]) % p + v1[k + k + 1] * v2[k + k + 1]  * (r - m) % p) % p) % p;
}

void insert2(int k, int l, int r, int x, int y, long long z) {
	if (l == x && r == y) {
		v1[k] = (v1[k] * z) % p;
		v2[k] = (v2[k] * z) % p;
		return;
	}
	if (v1[k]) 
		v1[k + k] = (v1[k + k] + v1[k]) % p, v1[k + k + 1] = (v1[k + k + 1] + v1[k]) % p, v1[k] = 0;
	if (v2[k] > 1) 
		v2[k + k] = (v2[k + k] * v2[k]) % p, v2[k + k + 1] = (v2[k + k + 1] * v2[k]) % p, v2[k] = 1;	
	int m = (l + r) >> 1;
	if (y <= m) insert2(k + k, l, m, x, y, z);
	else if (x > m) insert2(k + k + 1, m + 1, r, x, y, z);
	else insert2(k + k, l, m, x, m, z), insert2(k + k + 1, m + 1, r, m + 1, y, z);
	f[k] = (((f[k + k] * v2[k + k]) % p + v1[k + k] * v2[k + k] * (m - l + 1)) % p + ((f[k + k + 1] * v2[k + k + 1]) % p + v1[k + k + 1] * v2[k + k + 1] * (r - m) % p) % p) % p;
}

long long calc(int k, int l, int r, int x, int y) {
	if (l == x && r == y) 
		return ((f[k] * v2[k]) % p + v1[k] % p * (r - l + 1)) % p;
	if (v1[k]) 
		v1[k + k] = (v1[k + k] + v1[k]) % p, v1[k + k + 1] = (v1[k + k + 1] + v1[k]) % p, v1[k] = 0;
	if (v2[k] > 1) 
		v2[k + k] = (v2[k + k] * v2[k]) % p, v2[k + k + 1] = (v2[k + k + 1] * v2[k]) % p, v2[k] = 1;	
	int m = (l + r) >> 1;
	long long res = 0;
	if (y <= m) res = calc(k + k, l, m, x, y);
	else if (x > m) res = calc(k + k + 1, m + 1, r, x, y);
	else res = calc(k + k, l, m, x, m) + calc(k + k + 1, m + 1, r, m + 1, y);
	f[k] = (((f[k + k] * v2[k + k]) % p + v1[k + k] * (m - l + 1)) % p + ((f[k + k + 1] * v2[k + k + 1]) % p + (v1[k + k + 1] * (r - m)) % p) % p) % p;
	return res;
}

int main() {
	scanf("%d%d%d", &n, &q, &_);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	buildtree(1, 1, n);
	for (int i = 1; i <= q; i++) {
		int op, x, y;
		scanf("%d%d%d", &op, &x, &y);
		if (op == 1) {
			long long k;
			scanf("%lld", &k);
			insert2(1, 1, n, x, y, k);			
		} else if (op == 2) {
			long long k;
			scanf("%lld", &k);
			insert1(1, 1, n, x, y, k);	
		} else printf("%lld\n", calc(1, 1, n, x, y));
	}
	return 0;
}