Luogu1627 [CQOI2009]中位数

Luogu1627 [CQOI2009]中位数

给出一个 (n) 的排列，统计该排列有多少个长度为奇数的连续子序列的中位数是 (k)

(nleq10^5)

---

有关中位数的 (trick) ：因为不需要每个数的值，因此将原序列化为 (a_i=egin{cases}-1&(a_i<k)\0&(a_i=k)\1&(a_i>k)end{cases})

因此原问题就变成了

给出一个 (n) 的排列，统计该排列有多少个包含 (k) 的连续子序列的和为 (0)

即求 (displaystylesum_{i=1}^{pos}sum_{j=pos}^{n}[s_j-s_{i-1}=0])

所以我们只需枚举 (i) 并计数 (displaystylesum_{j=pos}^n[s_j=s_{i-1}])，暴力存一下即可

时间复杂度 (O(n))

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int n, k, a[maxn], s[maxn], c[maxn << 1];

int main() {
	scanf("%d %d", &n, &k);
	int pos; long long ans = 0;
	for (int i = 1, x; i <= n; i++) {
		scanf("%d", &x);
		if (x > k) a[i] = 1;
		if (x < k) a[i] = -1;
		if (x == k) a[i] = 0, pos = i;
		s[i] = s[i - 1] + a[i];
	}
	for (int i = pos; i <= n; i++) {
		c[s[i] + n]++;
	}
	for (int i = 1; i <= pos; i++) {
		ans += c[n + s[i - 1]];
	}
	printf("%lld", ans);
	return 0;
}