KMEDIAN - Above the Median - Solution for SPOJ

Problem

https://vn.spoj.com/problems/KMEDIAN

https://oj.vnoi.info/problem/KMEDIAN

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.

Example

Input  
6   
 
 
 
 
  
Output  


Explain: 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}.

Tutorial

Tóm đề: Cho N <= 10^5 số a[i] <= 10^9. Vị trí trung vị của một dãy liên tiếp i..j là : sau khi sort tăng dần dãy a[i..j] thì vị trí thứ m/2+1 (m là độ dài dãy) chính là vị trí trung vị. Yêu cầu đếm số lượng dãy con liên tiếp có giá trị tại vị trí trung vị >= K cho trước

Hướng dẫn:

Gọi f[i] là số lượng số >= k trong khoảng từ 1->i thì số lượng các số >= k trong khoảng từ i->j là f[j]-f[i-1].

Thuật cơ sở :

for j=1->n
    for i=1->j
        kiểm tra xem đoạn i..j có thỏa mãn không :

Điều kiện thỏa mãn là :

m = j-i+1 (chiều dài dãy) và t = f[j]-f[i-1] là số lượng các số >= k => m-t là số lượng các số < k.

điều kiện để vị trí trung vị >= k chính là

t >= m-t
    => 2t >= m
    => 2f[j]-f[i-1] >= j-i+1
    => 2f[j]-j-1 >= 2f[i-1]-i (*)

Đến đây thì chỉ việc dùng BIT để đếm và cập nhật các số thỏa (*). Mặc dù các số có giá trị < 2n nhưng có số âm nên phải nén số lại và chặt nhị phân tìm kiếm vị trí trên BIT.

Submission

KMEDIAN.cpp

Tutorial SPOJ

KMEDIAN - Above the Median