P12013 [Ynoi April Fool‘s Round 2025] 牢夸 Solution

Description

给定序列 $a=(a_1,a_2,\cdots ,a_n)$，有 $m$ 个操作分两种：

• $\mathrm{add}(l,r,k)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow a_i+v$.
• $\mathrm{query}(l,r)$：求 max ⁡ l ≤ u < v ≤ r { ∑ i = u v v − u + 1 } \max\limits_{l\le u<v\le r}\{\dfrac{\sum\limits_{i=u}^v}{v-u+1}\} l≤u<v≤rmax​{v−u+1i=u∑v​​}，以最简分数形式输出.

Limitations

$1\le n,m\le 10^6$
$|a_i|,|k|\le 10^3$
$1\le l\le r\le n$
$l\ne r$（for $\mathrm{query}$）
$5\text{s},512\text{MB}$

Solution

如果没有长度大于 $1$ 的限制，答案显然为最大值，所以我们推测：答案区间一定不会太长.
下面先证明一个引理：如果序列 $a$ 能分为两个子串 $b,c$，那么 $\bar{b}\ge \bar{a}$ 或 $\bar{c}\ge \bar{a}$.

考虑反证法，则有 $\frac{\sum b}{|b|},\frac{\sum c}{|c|}<\frac{\sum a}{|a|}=\frac{\sum b+\sum c}{|b|+|c|}$.
交叉相乘得：

• $(\sum b)\times (|b|+|c|)<(\sum b+\sum c)\times |b|$
• $(\sum c)\times (|b|+|c|)<(\sum b+\sum c)\times |c|$

相加得 $(\sum b+\sum c)\times (|b|+|c|)<(\sum b+\sum c)\times (|b|+|c|)$，矛盾.
故假设不成立，引理成立.

那么对于一个长度大于 $3$ 的子段，一定可以将其分为两个长度大于 $1$ 的子段，它们中至少有一个更优，所以最优的子段长度不大于 $3$.

知道这条就好办了，只需维护区间内长度为 $2,3$ 的子段最大和.
记 $b_i=a_i+a_{i-1},c_i=a_i+a_{i-1}+a_{i-2}$，用两棵线段树维护 $b,c$ 即可.
$\mathrm{add}$ 时细节很多，要小心，具体见代码.
时间复杂度 $O(m\log n)$.

Code

$3.44\text{KB},31.66\text{s},115.13\text{MB}\text{(in total, C++20 with O2)}$

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}

constexpr i64 inf = 1e18;
namespace seg_tree {
	struct Node {
		int l, r;
		i64 val, tag;
	};
	
	inline int ls(int u) { return 2 * u + 1; }
	inline int rs(int u) { return 2 * u + 2; }
	
	struct SegTree {
		vector<Node> tr;
		
		SegTree() {}
		SegTree(const vector<i64> &a) {
			const int n = a.size();
			tr.resize(n << 1);
			build(0, 0, n - 1, a);
		}
		
		void apply(int u, i64 c) {
			tr[u].val += c;
			tr[u].tag += c;
		}
		
		void pushup(int u, int mid) {
			tr[u].val = max(tr[ls(mid)].val, tr[rs(mid)].val);
		}
		
		void pushdown(int u, int mid) {
			if (!tr[u].tag) return;
			apply(ls(mid), tr[u].tag);
			apply(rs(mid), tr[u].tag);
			tr[u].tag = 0;
		}
		
		void build(int u, int l, int r, const vector<i64> &a) {
			tr[u].l = l, tr[u].r = r, tr[u].tag = 0;
			if (l == r) return (void)(tr[u].val = a[l]);
			const int mid = (l + r) >> 1;
			build(ls(mid), l, mid, a);
			build(rs(mid), mid + 1, r, a);
			pushup(u, mid);
		}
		
		void modify(int u, int l, int r, i64 c) {
			if (l <= tr[u].l && tr[u].r <= r) return apply(u, c);
			const int mid = (tr[u].l + tr[u].r) >> 1;
			pushdown(u, mid);
			if (l <= mid) modify(ls(mid), l, r, c);
			if (mid < r) modify(rs(mid), l, r, c);
			pushup(u, mid);
		}
		
		i64 query(int u, int l, int r) {
			if (l <= tr[u].l && tr[u].r <= r) return tr[u].val;
			i64 ans = -inf;
			const int mid = (tr[u].l + tr[u].r) >> 1;
			pushdown(u, mid);
			if (l <= mid) ans = max(ans, query(ls(mid), l, r));
			if (mid < r) ans = max(ans, query(rs(mid), l, r));
			return ans; 
		}
		
		void range_add(int l, int r, int v) { modify(0, l, r, v); }
		i64 range_max(int l, int r) { return query(0, l, r); }
	};
}
using seg_tree::SegTree;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n, m; scanf("%d %d", &n, &m);
	vector<i64> a(n), a2(n, -inf), a3(n, -inf);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &a[i]);
		if (i > 0) a2[i] = a[i] + a[i - 1];
		if (i > 1) a3[i] = a[i] + a[i - 1] + a[i - 2];
	}
	
	SegTree s2(a2), s3(a3);
	auto query = [&](int l, int r) -> pair<i64, i64> {
		const i64 r2 = s2.range_max(l + 1, r);
		const i64 r3 = (l + 2 <= r ? s3.range_max(l + 2, r) : -inf);
        i64 num = (r2 * 3 > r3 * 2) ? r2 : r3;
        i64 den = (r2 * 3 > r3 * 2) ? 2 : 3;
        if (num % den == 0) num /= den, den = 1;
        return {num, den};
	};
	
	auto add = [&](int l, int r, i64 x) {
		s2.range_add(l, l, x);
		s3.range_add(l, l, x);
        if (l + 1 <= r) {
            s2.range_add(l + 1, r, x * 2);
            s3.range_add(l + 1, l + 1, x * 2);
        }
        if (l + 2 <= r) {
            s3.range_add(l + 2, r, x * 3);
        }
        
        if (r + 1 < n) {
            s2.range_add(r + 1, r + 1, x);
            s3.range_add(r + 1, r + 1, l == r ? x : x * 2);
        }
        if (r + 2 < n) {
            s3.range_add(r + 2, r + 2, x);
        }
	};
	
	for (int i = 0, op, l, r, v; i < m; i++) {
		scanf("%d %d %d", &op, &l, &r), l--, r--;
		if (op == 1) {
			scanf("%d", &v);
			add(l, r, v);
		}
		else {
			auto [num, den] = query(l, r);
			printf("%lld/%lld\n", num, den);
		}
	}
	
	return 0;
}