2022.10.12-D 中位数

## 题意： 我们记一个长度为 $n$ 的序列的中位数是它**排序后** $\lfloor \frac{n}{2} \rfloor+1$ 位置上的数。 现在有一个长度为 $n$ 的序列 $a$，对于任意 $1\le l \le r \le n$，我们取出区间 $[l,r]$ 的中位数，记为 $b[l][r]$。 求 $b$ 的中位数。 $n \le 100000$ ------------ ## 思路： 首先我们求中位数有一个很套路的方法： - 我们二分一个数 $mid$，对于原序列中 $\ge mid$ 的数，我们标记为 $1$；反之，对于 $< mid$ 的数，我们标记为 $-1$。 - 标记结束后，我们对所有标记求和，记为 $sum$。如果 $sum \ge 0$，说明中位数是 $\ge mid$ 的，那么向右继续二分；反之，向左二分。 对于这题，我们思路一样是二分一个数 $mid$，并对原序列进行标记。 我们的问题就转化为：统计有多少个区间，其**标记和** $\ge 0$。 记满足条件的区间有 $cnt$ 个，如果 $cnt\ge \lfloor \frac{n(n+1)/2+1}{2} \rfloor$，那么说明 $ans\ge mid$，继续向右二分；反之向左二分。 现在来思考怎么计算这个 $cnt$。我们考虑对标记做一个**前缀和**，设为 $s$。 一个满足条件的区间 $[l,r]$ 需要 $s_r-s_{l-1}$。 这是一个经典的计数问题，用树状数组维护。 时间复杂度为 $O(n\log^2n)$ ------------ ## 代码 ```cpp #include<bits/stdc++.h> #define LL long long #define FOR(i, x, y) for(int i = (x); i <= (y); i++) #define ROF(i, x, y) for(int i = (x); i >= (y); i--) using namespace std; inline int rd() { int sign = 1, re = 0; char c = getchar(); while(!isdigit(c)){if(c == '-') sign = -1; c = getchar();} while(isdigit(c)) {re = re * 10 + (c - '0'); c = getchar();} return sign * re; } int n, a[100005], b[100005], s[100005]; LL tot; int tr[200005]; inline int lb(int x) {return x & (-x);} inline void add(int x, int val) { while(x <= (n << 1) + 1) { tr[x] += val; x += lb(x); } } inline int query(int x) { int re = 0; while(x) { re += tr[x]; x ^= lb(x); } return re; } inline bool chk(int mid) { LL re = 0; FOR(i, 1, n) if(a[i] < s[mid]) b[i] = -1; else b[i] = 1; FOR(i, 1, n) { b[i] += b[i - 1]; re += query(b[i] + n + 1); if(b[i] >= 0) re++; add(b[i] + n + 1, 1); } ROF(i, n, 1) add(b[i] + n + 1, -1); return re >= tot; } signed main() { n = rd(); tot = 1ll * n * (n + 1) / 2ll; tot = (tot + 1) / 2ll; FOR(i, 1, n) a[i] = s[i] = rd(); sort(s + 1, s + 1 + n); int l = 0, r = n + 1; while(l + 1 < r) { int mid = (l + r) >> 1; if(chk(mid)) l = mid; else r = mid; } printf("%d", s[l]); return 0; } ```