【洛谷U142585】中位数之中位数

题目

题目链接：https://www.luogu.com.cn/problem/U142585
给出一个长度为 (n) 的序列 (a)，首先求出其所有区间的中位数，将这些中位数构成的集合记为 (S)，求 (S) 中所有数的中位数。

这里定义的中位数指：对于 (m) 个数，将其从小到大排序后，第 ((frac{m}{2}+1)) 个数即为中位数，例如 ((10,30,20)) 的中位数为 (20)，((10,30,20,40)) 的中位数为 (30)，((10,10,10,20,30)) 的中位数为 (10)。

思路

套路性二分将序列转化为 (1,-1) 序列。
然后做一遍前缀和，问题转化为 (sum^{n}_{i=1}sum^{i-1}_{j=0}[s_i-s_jgeq 0]) 是否非负。
用树状数组计算一下即可。
时间复杂度 (O(nlog nlog A))。其中 (A=max(a_i))。

代码

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

const int N=200010;
int n,a[N],s[N];
ll sum;

struct BIT
{
	int c[N];
	
	void add(int x,int v)
	{
		for (int i=x;i<N;i+=i&-i)
			c[i]+=v;
	}
	
	int query(int x)
	{
		int sum=0;
		for (int i=x;i;i-=i&-i)
			sum+=c[i];
		return sum;
	}
}bit;

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int l=1,r=1e9,mid;
	while (l<=r)
	{
		mid=(l+r)>>1; sum=0; s[0]=1e5+1;
		memset(bit.c,0,sizeof(bit.c));
		bit.add(s[0],1);
		for (int i=1;i<=n;i++)
		{
			if (a[i]>=mid) s[i]=s[i-1]+1;
				else s[i]=s[i-1]-1;
			sum+=2*bit.query(s[i])-i;
			bit.add(s[i],1);
		}
		if (sum>=0) l=mid+1;
			else r=mid-1;
	}
	printf("%d
",l-1);
	return 0;
}