P12013 [Ynoi April Fool's Round 2025] 牢夸 题解

const ll N = 1e6 + 10, inf = 3e15;
ll a[N], sgtr2[N * 4], sgtr3[N * 4], tag2[N * 4], tag3[N * 4];

ll ls(ll p) {
	return p * 2;
}

ll rs(ll p) {
	return p * 2 + 1;
}

void pushup2(ll p) {
	sgtr2[p] = max(sgtr2[ls(p)], sgtr2[rs(p)]);
}

void pushup3(ll p) {
	sgtr3[p] = max(sgtr3[ls(p)], sgtr3[rs(p)]);
}

void pushdown2(ll p) {
	sgtr2[ls(p)] += tag2[p];
	sgtr2[rs(p)] += tag2[p];
	tag2[ls(p)] += tag2[p];
	tag2[rs(p)] += tag2[p];
	tag2[p] = 0;
}

void pushdown3(ll p) {
	sgtr3[ls(p)] += tag3[p];
	sgtr3[rs(p)] += tag3[p];
	tag3[ls(p)] += tag3[p];
	tag3[rs(p)] += tag3[p];
	tag3[p] = 0;
}

void build(ll p, ll l, ll r) {
	if (l == r) {
		sgtr2[p] = a[l] + a[l + 1];
		sgtr3[p] = a[l] + a[l + 1] + a[l + 2];
		return;
	}

	ll mid = (l + r) / 2;
	build(ls(p), l, mid);
	build(rs(p), mid + 1, r);
	pushup2(p);
	pushup3(p);
}

void upd2(ll p, ll l, ll r, ll ql, ll qr, ll val) {
	if (ql > r or qr < l)
		return;

//	cout << "upd2:" << l << " " << r << '\n';
//	pause;

	if (ql <= l and r <= qr) {
		sgtr2[p] += val;
		tag2[p] += val;
		return;
	}

	ll mid = (l + r) / 2;

	if (tag2[p])
		pushdown2(p);

	upd2(ls(p), l, mid, ql, qr, val);
	upd2(rs(p), mid + 1, r, ql, qr, val);
	pushup2(p);
}

void upd3(ll p, ll l, ll r, ll ql, ll qr, ll val) {
	if (ql > r or qr < l)
		return;

//	cout << "upd3:" << l << " " << r << '\n';
//	pause;

	if (ql <= l and r <= qr) {
		sgtr3[p] += val;
		tag3[p] += val;
		return;
	}

	ll mid = (l + r) / 2;

	if (tag3[p])
		pushdown3(p);

	upd3(ls(p), l, mid, ql, qr, val);
	upd3(rs(p), mid + 1, r, ql, qr, val);
	pushup3(p);
}

ll query2(ll p, ll l, ll r, ll ql, ll qr) {
	if (ql > r or qr < l)
		return -inf;

	if (ql <= l and r <= qr)
		return sgtr2[p];

	ll mid = (l + r) / 2;

	if (tag2[p])
		pushdown2(p);

	return max(query2(ls(p), l, mid, ql, qr), query2(rs(p), mid + 1, r, ql, qr));
}

ll query3(ll p, ll l, ll r, ll ql, ll qr) {
	if (ql > r or qr < l)
		return -inf;

	if (ql <= l and r <= qr)
		return sgtr3[p];

	ll mid = (l + r) / 2;

	if (tag3[p])
		pushdown3(p);

	return max(query3(ls(p), l, mid, ql, qr), query3(rs(p), mid + 1, r, ql, qr));
}

ll n, q;

int main() {
	cin >> n >> q;

	rep(i, 1, n) cin >> a[i];

	build(1, 1, n);

	count(q) {
		ll ty, l, r, val;
		cin >> ty;

		if (ty == 1) {
			cin >> l >> r >> val;

			if (r - 1 >= l)
				upd2(1, 1, n, l, r - 1, val * 2);

			upd2(1, 1, n, r, r, val);

			if (l - 1 >= 1)
				upd2(1, 1, n, l - 1, l - 1, val);

			if (r - 2 >= l)
				upd3(1, 1, n, l, r - 2, val * 3);

			if (r - 1 >= l)
				upd3(1, 1, n, r - 1, r - 1, val * 2);

			upd3(1, 1, n, r, r, val);

			if (l >= 2) {
				if (r - l + 1 >= 2)
					upd3(1, 1, n, l - 1, l - 1, val * 2);
				else
					upd3(1, 1, n, l - 1, l - 1, val);
			}

			if (l >= 3)
				upd3(1, 1, n, l - 2, l - 2, val);

//			cout << query2(1, 1, n, 4, 5) << '\n';
//			pause;
		} else {
			cin >> l >> r;
			ll fm, fz, ans2 = query2(1, 1, n, l, r - 1), ans3 = -inf;

			if (l <= r - 2)
				ans3 = query3(1, 1, n, l, r - 2);

//			cout << "ans2=" << ans2 << ",ans3=" << ans3 << '\n';
//			pause;

			if (ans2 * 1.0 / 2 >= ans3 * 1.0 / 3) {
				fz = ans2;
				fm = 2;
			} else {
				fz = ans3;
				fm = 3;
			}

			if (fz == 0) {
				cout << "0/1\n";
				ctn;
			}


			if (fz < 0) {
				cout << "-";
				fz *= -1;
			}

			ll temp = __gcd(fz, fm);
			fz /= temp;
			fm /= temp;

			cout << fz << "/" << fm << '\n';
		}
	}
}