题意:
题目链接
给一个长为N的序列,求出所有子区间中位数组成的新序列的中位数
思路:
首先我们需要找到这个题的可二分性:
- 我们可以知道中位数的性质:
在序列中,比中位数小的个数有差不多N/2个,呢么比中位数大的差不多也有N/2个,由此我们找到了可二分性
,所以我们就可以二分答案
- 得到序列中所有中位数比mid大的区间个数:
(1) 首先利用前缀和处理数组,将不小于mid的赋为1,其余赋为-1,这样我们就可以得到原序列中的前缀区间的值
(2) 利用树状数组求前缀和位置的所有顺序对数,这样就可以求出中位数大于mid的区间个数
- 参考代码:*
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
| #include <cstdio> #include <algorithm> #include <vector> #include <iostream> #include <map> #include <queue> #include <cstring> #include <string> #include <cstdlib> #include <cmath> #include <set> using namespace std; const int inf = (1 << 30); typedef long long ll; const ll maxn = 1e5 + 5; vector<ll> vec; ll n, sum[maxn * 10], c[maxn * 10], a[maxn]; ll lowbit(ll x) { return x & (-x); } void modify(ll i) { while (i <= 2 * maxn) { ++c[i]; i += lowbit(i); } } ll getsum(ll i) { ll res = 0; while (i > 0) { res += c[i]; i -= lowbit(i); } return res; } bool check(ll mid) { memset(c, 0, sizeof c); for (ll i = 1; i <= n; i++) sum[i] = sum[i - 1] + (a[i] >= mid ? 1 : -1); ll res = 0; for (ll i = 0; i <= n; i++) { res += getsum(sum[i] + maxn); modify(sum[i] + maxn); } if (res >= ((n + 1) * n / 4)) return true; return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); ll l = 0, r = 0; cin >> n; for (ll i = 1; i <= n; i++) cin >> a[i], r = max(r, a[i]); ll ans = 0; while (l <= r) { ll mid = l + r >> 1; if (check(mid)) l = mid + 1, ans = mid; else r = mid - 1; } cout << ans << endl; }
|