AtCoder Beginner Contest 107(D -

链接：https://abc107.contest.atcoder.jp/tasks/arc101_b
思路：我感觉是道神仙题， 我要在这里手动膜一下余大神！！！！口解题目tql！！！，首先不可能硬求中位数，我们考虑，如果所有的数为0和1的解法，那么我们可以考虑把0变为-1，然后对所有位置求前缀和，某两个前缀和后减前如果大于0则说明这个区间1更多（中位数是1），有了这个想法，我们就想到了可以用二分枚举，比当前枚举值大或者相等的设为1，小的设为-1，，然后用01的求法求解当前问题，算出逆序数，用总数-逆序和-（遍历1-n中<0的前缀和）就可以得到和大于等于0的区间数目，只要这个数目比总和数目的一半大就说明这个枚举值偏小，对应就行二分即可。细节很多写的时候注意，求逆序数用分治写的，还不太会用树状数组求后面来补一下这个地方= =
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+10;
int a[maxn];
int b[maxn];
int n;

int c[maxn],tmp[maxn];
long long ans;

void Merge(int l,int m,int r)
{
    int i = l;
    int j = m + 1;
    int k = l;
    while(i <= m && j <= r)
    {
        if(c[i] > c[j])
        {
            tmp[k++] = c[j++];
            ans += m - i + 1;
        }
        else
        {
            tmp[k++] = c[i++];
        }
    }
       while(i <= m) tmp[k++] = c[i++];
    while(j <= r) tmp[k++] = c[j++];
    for(int i=l;i<=r;i++)
        c[i] = tmp[i];
}
 
void Merge_sort(int l,int r)
{
    if(l < r)
    {
        int m = (l + r) >> 1;
        Merge_sort(l,m);
        Merge_sort(m+1,r);
        Merge(l,m,r);
    }
}

int lowbit(int x){
    return x&(-x);
}

void add(int x,int d){
    while(x<=n){
        b[x]+=d;
        x+=lowbit(x);
    }
}


int sum(int x){
    int res = 0;
    while(x){
        res+=b[x];
        x-=lowbit(x);
    }
    return res;
}

bool cc(int d){
    memset(b,0,sizeof(b));
for(int i=1;i<=n;i++){
    if(a[i]>=d)add(i,1);
    else add(i,-1);
}
    for(int i=1;i<=n;i++)c[i] = sum(i);
        ans = 0;
        for(int i=1;i<=n;i++){
            if(c[i]<0)ans++;//单个前缀和小于0
        }
        Merge_sort(1,n);//统计逆序数
        long long num = 1LL*n*(n+1)/2 - ans;
        return num>=ans;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int ub = 1e9;
    int lb = 0;
        while(ub-lb>1){
            int mid = lb+(ub-lb)/2;
            if(cc(mid))lb = mid;
            else ub = mid;
        }
        if(cc(lb+1))lb++;
        printf("%d\n",lb);
    return 0;
}