题解 [CQOI2009] 中位数

题目链接

要想使得数字 \(x\) 是中位数，就必须选出 \(k\) 个小于 \(x\) 的数和 \(k\) 个大于 \(x\) 的数。

我们考虑对数字附上特殊值，小于 \(x\) 的数赋值为 \(-1\)，大于 \(x\) 的数赋值为 \(1\)，\(x\) 则赋值为 \(0\)，那么若一段包含 \(x\) 的连续序列的和等于 \(0\)，就可以说明这段连续序列是合法的。

对于区间求和，考虑前缀和优化。并注意一定是统计跨越 \(x\) 的区间和，辅助 \(map\) 统计一下即可。

总结：类似于这种要求某两种数字之间关系的，考虑赋值，如求 \(a\) 出现的次数大于 \(b\)，那么将 \(a\) 赋值为 \(1\)，\(b\) 赋值为 \(-1\)，那么就是总和大于 \(0\)。

const int N=110000;
int n,m,p;
int a[N],sum[N];
map<int,int> cnt;

int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==m) {sum[i]=sum[i-1]; p=i;}
		else if(a[i]<m) sum[i]=sum[i-1]-1;
		else sum[i]=sum[i-1]+1;
	}
	for(int i=0;i<=p-1;i++) cnt[sum[i]]++;
	LL ans=0;
	for(int i=p;i<=n;i++) {
		ans+=cnt[sum[i]];
	}
	cout<<ans;
	return 0;
}