题解 P1627 【[CQOI2009]中位数】
Heartlessly
2019-02-13 19:52:30
## Description:
给定长度为 $n$ 的序列，求有多少奇数长度的序列中位数为 $b$ 。
------------
## Solution:
因为所求的是中位数，所以考虑改变原序列。把大于 $b$ 的数全部变为 $1$，小于 $b$ 的数变为 $-1$，等于 $b$ 则为 $0$。问题就变为求存在几个包含 $b$ 的区间和为 $0$ 。我们假设 $tmp$ 为 $b$ 的下标，原数组为 $x$，新数组为 $a$ 。
### Sample Input:
```
7 4
5 7 2 4 3 1 6
```
### Example:
能使结果成立的区间分别为 $[1,5]$ , $[1,7]$ , $[2,4]$ , $[4,4]$。
接下来我们建造两个桶，分别计数 $tmp$ 左边的后缀和与右边的前缀和，假设左边的后缀和为 $l$，右边的前缀和为 $r$ 。$l[i]/r[i]$ 表示从点 $i$ **向右/向左** 到点 $tmp$ 为止 (比 $b$ 大的数的数量 - 比 $b$ 小的数的数量) 出现的次数。还是拿样例来说：
通过观察上图，我们能够发现，左边的数 $x$ 可以与右边的每一个 $-x$ 进行匹配。通过乘法原理，该值即为 $l[x] \times r[-x]$，由题意可知 $-10^5 \le x \le 10^5$，遍历所有的 $x$ 即可，最终答案为 $\sum_{i=min}^{max}l[i] \times r[-i]$ 。
值得注意的是，$l[0]$ 和 $r[0]$ 的初始值为 $1$，因为 $b$ 是需要被算入的。当然，桶的下标不能是负数，所以我在每次操作时都加上了一个很大的数，即数据最大值 —— $10^5$，也可以用 $STL$ 中的 $map$ 解决问题，时间复杂度为 $O(n)$ 。
------------
## Code
```cpp
/*
Language:C++
Author:xuxing
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template < class T > inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
x = f ? -x : x;
}
const int maxN = 1e5;
LL n, b, x, tmp, sum, ans, a[maxN + 10], l[maxN << 2], r[maxN << 2];
int main() {
read(n), read(b);
for (LL i = 1; i <= n; i++) { read(x); if (x == b) tmp = i; else a[i] = x > b ? 1 : -1; }//初始化
l[maxN] = 1, r[maxN] = 1;
for (LL i = tmp - 1; i >= 1; i--) { sum += a[i]; l[sum + maxN]++; }//后缀和统计
sum = 0;
for (LL i = tmp + 1; i <= n; i++) { sum += a[i]; r[sum + maxN]++; }//前缀和统计
for (LL i = 0; i <= (maxN << 1); i++) { if (l[i] && r[(maxN << 1) - i]) ans += l[i] * r[(maxN << 1) - i]; }//累加答案
printf("%lld\n", ans);
return 0;
}
```