当前位置：首页 > news >正文

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

news 来源：原创 2025/9/7 5:09:25

Description

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

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

Limitations

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

Solution

如果没有长度大于 $1$ 的限制，答案显然为最大值，所以我们推测：答案区间一定不会太长.
下面先证明一个引理：如果序列 $a$ 能分为两个子串 $b, c$ ，那么 $\bar{b}\ge\bar{a}$ 或 $\bar{c}\ge\bar{a}$ .
考虑反证法，则有 $\dfrac{\sum b}{|b|},\dfrac{\sum c}{|c|}<\dfrac{\sum a}{|a|}=\dfrac{\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$ 即可.
$\operatorname{add}$ 时细节很多，要小心，具体见代码.
时间复杂度 $O(m\log n)$ .

Code

$3.44\text{KB},31.66\text{s},115.13\text{MB}\;\texttt{(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;
}

Description

Limitations

Solution

Code

相关文章：