题解：CF2126G2 Big Wins! (hard version)

· · 题解

题解：CF2126G Big Wins!

一、题意

给定一个长度为 n 的正整数序列 a，让你求它的任意子段中中位数减去最小值的最大值，多组数据。

数据范围：

二、解法（G1）

很好的题，可惜没有场切。

我们约定一个区间的中位数为 \text{med}，最小值为 \text{min}。

刚看到题，肯定能想到一个 O(n^3) 的暴力，但是这复杂度肯定就爆炸了。

一定是题目有什么特殊的性质，也许就蕴含在 \text{med} 和 \text{min} 当中？

先考虑 \text{min}，我们知道一个数是 \text{min} 统治的是一段区间。

所以赛时想的是枚举 $\text{min}$，然后在其统治区间里面找到最大的 $\text{med}$。 但这是 $O(n^2)$ 的，所以考场上遗憾离场。 事实上，$\text{med}$ 有一个经典的 trick，我们可以在非常可观的复杂度上判断一段数的中位数是否大于等于钦定的 $\text{med}$ 。 算法：我们把所有大于等于 $\text{med}$ 的数字变成 $1$，其他的变成 $-1$，如果一段的区间和非负，则这一段的中位数大于等于 $\text{med}$。 有点像二分的 $\text{check}$ 函数。 正确性可以自己理解。 考虑特殊性质，$\text{med} \le 100$ 的条件似乎是要我们枚举 $\text{med}$ ？ 不妨考虑枚举 $\text{med}$，那我们只要找到区间中位数大于等于 $\text{med}$ 的最小值就可以了。 实际做法：先预处理每个数统治的最小值区间（设为 $L_i$ 和 $R_i$），然后枚举 $\text{med}$ 后把 $p$ 序列（$1/-1$ 序列的前缀和）更新，接着我们可以用一个数据结构（比如 $\text{st}$ 表）来处理区间 $p$ 的最大最小值，每次判断 $a_i$ 能不能选就直接用一个式子 $\max(p_j) - \min(p_k) \ge 0$，$j \in [i,R_i]$，$k \in [L_i-1,i)$ 判断即可。 复杂度 $O(n \log n \cdot \text{maxV})$ 可以通过。 ### 三、解法（G2） 考虑 G1 在做什么。 我们其实就是在枚举 $\text{med}$ 的时候看看能取到的最小值。 其实把这个放在 G2 的条件下也可以做。 我们先预处理，把所有的 $(a_i,i)$ 从小到大排序，枚举 $\text{med}$，然后用线段树维护 $p$，因为一个子段是否可以被用具有二分性，就可以用一个指针 point 维护现在可以取到的最小 $\text{min}$ 即可。 复杂度 $O(n \log n)$。 代码： ```cpp #include <bits/stdc++.h> using namespace std; #define ll long long #define LL __int128 #define ull unsigned long long #define pii pair < int , int > #define mp(i, j) make_pair(i, j) #define l(o) (o << 1) #define r(o) (o << 1 | 1) #define mid (l + r >> 1) const int N = 2e5 + 5, M = 524300; int T, n, a[N], l[N], r[N]; vector < int > vec[N]; struct node { int val, id; } b[N]; bool cmp(node a, node b) { return a.val < b.val; } struct Segtree { int ma[M], mn[M], tag[M]; void pushup(int o) { ma[o] = max(ma[l(o)], ma[r(o)]); mn[o] = min(mn[l(o)], mn[r(o)]); } void build(int o, int l, int r) { tag[o] = 0; if(l == r) { ma[o] = mn[o] = l; return; } build(l(o), l, mid), build(r(o), mid + 1, r); pushup(o); } void pushdown(int o) { if(!tag[o]) return; tag[l(o)] += tag[o], tag[r(o)] += tag[o]; ma[l(o)] += tag[o], ma[r(o)] += tag[o]; mn[l(o)] += tag[o], mn[r(o)] += tag[o]; tag[o] = 0; } void add(int o, int l, int r, int ql, int qr, int x) { if(ql <= l && r <= qr) { ma[o] += x, mn[o] += x, tag[o] += x; return; } pushdown(o); if(ql <= mid) add(l(o), l, mid, ql, qr, x); if(qr > mid) add(r(o), mid + 1, r, ql, qr, x); pushup(o); } int Max(int o, int l, int r, int ql, int qr) { if(ql <= l && r <= qr) return ma[o]; pushdown(o); int ans = -1e9; if(ql <= mid) ans = max(ans, Max(l(o), l, mid, ql, qr)); if(qr > mid) ans = max(ans, Max(r(o), mid + 1, r, ql, qr)); return ans; } int Min(int o, int l, int r, int ql, int qr) { if(ql <= l && r <= qr) return mn[o]; pushdown(o); int ans = 1e9; if(ql <= mid) ans = min(ans, Min(l(o), l, mid, ql, qr)); if(qr > mid) ans = min(ans, Min(r(o), mid + 1, r, ql, qr)); return ans; } } tree; int main() { scanf("%d", &T); while(T --) { scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[i] = (node) { a[i], i }; vec[a[i]].clear(); l[i] = r[i] = 0; } for(int i = 1; i <= n; i++) vec[a[i]].push_back(i); tree.build(1, 1, n); sort(b + 1, b + 1 + n, cmp); a[0] = a[n + 1] = 0; stack < int > st; st.push(0); for(int i = 1; i <= n; i++) { while(!st.empty() && a[st.top()] >= a[i]) st.pop(); l[i] = st.top(), st.push(i); } while(!st.empty()) st.pop(); st.push(n + 1); for(int i = n; i >= 1; i--) { while(!st.empty() && a[st.top()] >= a[i]) st.pop(); r[i] = st.top(), st.push(i); } int p = 1, num = 0, ans = 0; for(int med = 1; med <= n; med++) { if(b[med].val > num) { for(int i : vec[num]) tree.add(1, 1, n, i, n, -2); num = b[med].val; } while(p <= n) { int ma = tree.Max(1, 1, n, b[p].id, r[b[p].id] - 1); int mn = 1e9; if(b[p].id > 1) mn = tree.Min(1, 1, n, max(l[b[p].id], 1), b[p].id - 1); else mn = 0; if(!l[b[p].id]) mn = min(mn, 0); if(ma - mn < 0) p ++; else break; } if(p > n) break; ans = max(ans, b[med].val - b[p].val); // cout << "ans = " << ans << endl; } printf("%d\n", ans); } return 0; } ``` ### 四、总结 这道题的核心营养点就是 $\text{med}$ 的套路，每次从小到大枚举然后维护 $p$。