BSOJ3686 -- 【USACO 2011 November Gold】Above the Median【树状数组统计】

dzy posted @ 2013年8月07日 20:24 in BSOJ with tags usaco 树状数组 , 1343 阅读

 

Description

Farmer John has lined up his N (1 <= N <= 100,000) cows in a row to measure their heights; cow i has height H_i (1 <= H_i <= 1,000,000,000) nanometers--FJ believes in precise measurements! He wants to take a picture of some contiguous subsequence of the cows to submit to a bovine photography contest at the county fair. 

The fair has a very strange rule about all submitted photos: a photograph is only valid to submit if it depicts a group of cows whose median height is at least a certain threshold X (1 <= X <= 1,000,000,000).

For purposes of this problem, we define the median of an array A[0...K] to be A[ceiling(K/2)] after A is sorted, where ceiling(K/2) gives K/2 rounded up to the nearest integer (or K/2 itself, it K/2 is an integer to begin with). For example the median of {7, 3, 2, 6} is 6, and the median of {5, 4, 8} is 5.

Please help FJ count the number of different contiguous subsequences of his cows that he could potentially submit to the photography contest.

Input

* Line 1: Two space-separated integers: N and X.
* Lines 2..N+1: Line i+1 contains the single integer H_i.

Output

* Line 1: The number of subsequences of FJ's cows that have median at least X. Note this may not fit into a 32-bit integer.

Sample Input

4 6
10
5
6
2

INPUT DETAILS:

FJ's four cows have heights 10, 5, 6, 2. We want to know how many contiguous subsequences have median at least 6.

Sample Output

7

OUTPUT DETAILS:

There are 10 possible contiguous subsequences to consider. Of these, only 7 have median at least 6. They are {10}, {6}, {10, 5}, {5, 6}, {6, 2}, {10, 5, 6}, {10, 5, 6, 2}.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

题意:统计有几个连续子段的中位数(A[1..k]从大到小排序后A[k/2向上取整])大于等于给定值m。

 

应该还是比较好搞的。

把大于等于m的标记为1。小于m的标记为-1。

我们就只需要统计连续子段和非负的个数。

树状数组搞即可。

(新本本好好用。呵呵呵。)

 

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=210000,d=100010;
int n,m,a[100010],bit[maxn+10]; 
void modify(int x){
	for(;x<=maxn;x+=x&-x)	bit[x]++;
}
int ask(int x){
	int r=0;
	for(;x;x-=x&-x)	r+=bit[x];
	return r;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]>=m)	a[i]=1;	else a[i]=-1;
	}
	int sum=0;
	long long An=0;
	modify(d);
	for(int i=1;i<=n;i++){
		sum+=a[i];
		An+=1ll*ask(sum+d);
		modify(sum+d);
	}
	cout << An << endl;
	return 0;
}

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter