@Median of Medians@

@题目描述 - English@

Time limit : 2sec / Memory limit : 1024MB

Score : 700 points

Problem Statement
We will define the median of a sequence b of length M, as follows:

Let b’ be the sequence obtained by sorting b in non-decreasing order. Then, the value of the (M/2+1)-th element of b’ is the median of b. Here, /is integer division, rounding down.
For example, the median of (10,30,20) is 20; the median of (10,30,20,40) is 30; the median of (10,10,10,20,30) is 10.

Snuke comes up with the following problem.

You are given a sequence a of length N. For each pair (l,r) (1≤l≤r≤N), let ml,r be the median of the contiguous subsequence (al,al+1,…,ar) of a. We will list ml,r for all pairs (l,r) to create a new sequence m. Find the median of m.

Constraints
1≤N≤10^5
ai is an integer.
1≤ai≤10^9

Input
Input is given from Standard Input in the following format:
N
a1 a2 … aN

Output
Print the median of m.

Sample Input 1
3
10 30 20
Sample Output 1
30

The median of each contiguous subsequence of a is as follows:
The median of (10) is 10.
The median of (30) is 30.
The median of (20) is 20.
The median of (10,30) is 30.
The median of (30,20) is 30.
The median of (10,30,20) is 20.
Thus, m=(10,30,20,30,30,20) and the median of m is 30.

Sample Input 2
1
10
Sample Output 2
10

Sample Input 3
10
5 9 5 9 8 9 3 5 4 3
Sample Output 3
8

@题目大意@

给定一个序列，中位数定义为序列排完序后第（序列长度/2 + 1）个数（向下取整），给定序列所有子序列的中位数构成新序列M，求M的中位数。

@分析@

【首先吐槽一下……感觉Atcoder的比赛题目名都还挺有意思的，并且内容并没有和题目名不相干，给出题人点个赞】
【说不定下一次又出来一个Average of Averages】
【Mode of Modes好像也可以……等一下好像扯远了】

首先可以发现的是，这道题不能将M构造出来然后进行求解。考虑怎么在不求解M的情况下求出中位数，我们发现其实可以用二分答案的方法，求出最小的x满足“小于等于x的数至少有（序列长度/2 + 1）个”，这样子x就一定是中位数。
问题转化为怎么进行判定，即：“有多少个区间的中位数小于等于x”。
对于二分出来的答案x，将原序列上所有大于x的数记为-1，小于等于x的数记为1，问题进一步转化为：“有多少个序列至少有（序列长度/2 + 1）个1”，可以发现它等价于“有多少个序列的和是正数”。
在修改过后的原序列上做前缀和，序列[l, r]的和 = sum[r] - sum[l-1]。如果该式为正数，则sum[r] > sum[l-1]。
那么，对于所有的sum[x] > sum[y]，如果再满足x > y，则[y+1, x]这个序列就是一个合法序列。上面的条件其实就是一个二维偏序问题，可以用归并排序（或者有人喜欢可以叫做“CDQ分治”）解决。
至此，本问题得以在O(nlog^2n)的时间复杂度内解决。
【附上一段聊天记录】

@代码实现@

如果大家对于上面的思路仍不是很懂，可以参考代码或者留言在下面问我qwq。

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 100000;
const int INF = int(1E9);
int arr[MAXN + 5], sum[MAXN + 5], temp[MAXN + 5];
long long tot1 = 0, tot2 = 0;
int N;
void MergeSort(int le, int ri) {
    if( le == ri ) return ;
    int mid = (le + ri) >> 1;
    MergeSort(le, mid);
    MergeSort(mid+1, ri);
    int p = le, q = mid+1, r = le;
    while( p <= mid && q <= ri ) {
        if( sum[p] < sum[q] ) {
            temp[r++] = sum[p++];
        }
        else {
            tot1 += (p-le);
            temp[r++] = sum[q++];
        }
    }
    while( p <= mid ) {
        temp[r++] = sum[p++];
    }
    while( q <= ri ) {
        tot1 += (p-le);
        temp[r++] = sum[q++];
    }
    for(int i=le;i<=ri;i++)
        sum[i] = temp[i];
}
bool Check(int x) {
    tot1 = 0;
    for(int i=1;i<=N;i++)
        sum[i] = (arr[i] <= x ? 1 : -1);
    for(int i=1;i<=N;i++)
        sum[i] += sum[i-1];
    MergeSort(0, N);
    return tot1 >= (tot2/2 + 1);
}
int main() {
    int le = INF, ri = -INF;
    scanf("%d", &N);
    for(int i=1;i<=N;i++) { 
        scanf("%d", &arr[i]);
        le = min(le, arr[i]);
        ri = max(ri, arr[i]);
        tot2 += i;
    }
    while( le < ri ) {
        int mid = (le + ri) >> 1;
        if( Check(mid) ) ri = mid;
        else le = mid + 1;
    }
    printf("%d\n", ri);
}

@END@

就是这样，新的一天里，也请多多关照哦(ノω<。)ノ))☆.。~