网络备案信息查询_seo课程哪个好_站外推广免费网站_考证培训机构报名网站

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;
}