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

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

 

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;
}

 

 

Avatar_small
Zachary Chelmsford 说:
2019年2月18日 16:22

The worth of the programmer is filled for the accumulation for the people. The new features of the program and online academic essay writing are introduced for the candidates. The rate is depicted for the motive of the joy and its image for the humans.


登录 *


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