Zirnc's Blog
关于 分类 友链 存档 标签

D - Median of Medians

题意

给定一个整数序列 a[1],a[2],….a[n]a[1],a[2],….a[n]，那么对于 aa 序列的任意一个连续子序列 a[L],a[L+1],……a[R]a[L],a[L+1],……a[R]，其中 1<=L<=R<=n1<=L<=R<=n, 求出该连续子序列的中位数，记为 b[L][R]b[L][R]。

显然 bb 数组共有 n∗(n+1)/2n*(n+1)/2 个整数。

输出 bb 数组的中位数。

分析

关于中位数有一个 Trick：

  • 我们二分一个数 midmid，对于原序列中 ≥mid\ge mid 的数，我们标记为 11；反之，对于 <mid< mid 的数，我们标记为 −1−1。
  • 标记结束后，如果一个区间内的标记和大于等于 00，说明中位数大于等于 midmid，那么向右二分；反之向左。

对于本题，我们对 bb 数组二分它的中位数 midmid，并按 midmid 对 aa 数组进行 +1,−1+1,-1 标记。然后问题就变为了：统计有多少个区间的标记和 ≥0\ge 0。

记这个区间数为 cntcnt，若 cnt≥⌊n(n+1)/2+12⌋cnt\ge \lfloor \frac{n(n+1)/2+1}{2} \rfloor，说明 bb 数组实际中位数 ≥mid\ge mid，向右二分。否则向左二分。

怎么求有多少个区间的标记和 ≥0\ge 0 呢？我们可以做一个前缀和 ss，统计 i<ji < j 且 s[i]≤s[j]s[i] \le s[j] 的个数。这是一个二维偏序问题，可以搭配树状数组解决。

O(nlog2n)O(nlog^2n)。

 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

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
int a[100005], b[100005], t[100005], s[100005], tree[200005];
int lowbit(int x) { return x&(-x); }
void add(int x) {
	while (x <= 2*n+1) {
		tree[x]++;
		x += lowbit(x);
	}
}
ll query(int x) {
	ll s = 0;
	while (x) {
		s += tree[x];
		x -= lowbit(x);
	}
	return s;
}
int read(){
	int s = 0, f = 1;
	char c = getchar();
	while (!isdigit(c)) {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (isdigit(c)) {
		s = s*10+c-'0';
		c = getchar();
	}
	return s*f;
}
bool check(int x) {
	ll cnt = 0;
	for (int i = 1; i <= n; i++) {
		t[i] = a[i]>=x ? -1 : 1;
		s[i] = s[i-1]+t[i];
	}
	memset(tree, 0, sizeof tree);
	add(n+1);
	for (int i = 1; i <= n; i++) {
		cnt += query(s[i]+n);
		add(s[i]+n+1); 
	}
	return cnt >= (ll)n*(n+1)/4+1;
}
int main()
{
	n = read();
	for (int i = 1; i <= n; i++) a[i] = b[i] = read();
	sort(b+1, b+1+n);
	int L = 0, R = n+1;
	while (L + 1 < R) {
		int M = (L+R)>>1;
		if (check(b[M])) {
			R = M;
		} else {
			L = M;
		}
	}
	cout << b[L] << endl;
	return 0;
}

@ 2022/10/15 SM 模拟赛。