CQOI2009 中位数

wjh15101051's space

卧薪尝胆，厚积薄发。

CQOI2009 中位数

Date: Wed Sep 05 17:47:31 CST 2018

In Category: NoCategory

Description：

给出 $1$ ~ $n$ 的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是 $b$ 。

$1\le n \le 100000$

Solution：

找出 $b$ 的位置 $pos$ ，向左向右统计出比它大的有 $i$ 个（负数代表比他小）的位置的个数 $a[i]$ ，统计答案时枚举左边是多少右边相反求和即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,b;

#define MAXN 100010

int a[MAXN];

int pos;

int lef[MAXN << 1],*l = lef + MAXN,rig[MAXN << 1],*r = rig + MAXN;

int main()

{

	scanf("%d%d",&n,&b);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&a[i]);

		if(a[i] == b)pos = i; 

	}

	for(int i = pos,cur = 0;i >= 1;--i)

	{

		if(a[i] < b)++cur;

		if(a[i] > b)--cur;

		++l[cur];

	}

	for(int i = pos,cur = 0;i <= n;++i)

	{

		if(a[i] < b)++cur;

		if(a[i] > b)--cur;

		++r[cur];

	}

	long long ans = 0;

	for(int i = -n;i <= n;++i)

	{

		ans = ans + l[i] * r[-i];

	}

	cout << ans << endl;

	return 0;

}

In tag: 其他-其他

wjh15101051