题意：

我们记一个长度为 $n$ 的序列的中位数是它排序后 $\lfloor \frac{n}{2} \rfloor+1$ 位置上的数。

现在有一个长度为 $n$ 的序列 $a$，对于任意 $1\le l \le r \le n$，我们取出区间 $[l,r]$ 的中位数，记为 $b[l][r]$。

求 $b$ 的中位数。 $n \le 100000$

---

思路：

首先我们求中位数有一个很套路的方法：

• 我们二分一个数 $mid$，对于原序列中 $\ge mid$ 的数，我们标记为 $1$；反之，对于 $< mid$ 的数，我们标记为 $-1$。

• 标记结束后，我们对所有标记求和，记为 $sum$。如果 $sum \ge 0$，说明中位数是 $\ge mid$ 的，那么向右继续二分；反之，向左二分。

对于这题，我们思路一样是二分一个数 $mid$，并对原序列进行标记。

我们的问题就转化为：统计有多少个区间，其标记和 $\ge 0$。

记满足条件的区间有 $cnt$ 个，如果 $cnt\ge \lfloor \frac{n(n+1)/2+1}{2} \rfloor$，那么说明 $ans\ge mid$，继续向右二分；反之向左二分。

现在来思考怎么计算这个 $cnt$。我们考虑对标记做一个前缀和，设为 $s$。

一个满足条件的区间 $[l,r]$ 需要 $s_r-s_{l-1}$。

这是一个经典的计数问题，用树状数组维护。

时间复杂度为 $O(n\log^2n)$

---

代码

#include<bits/stdc++.h>
#define LL long long
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
using namespace std;
inline int rd()
{
    int sign = 1, re = 0; char c = getchar();
    while(!isdigit(c)){if(c == '-') sign = -1; c = getchar();}
    while(isdigit(c)) {re = re * 10 + (c - '0'); c = getchar();}
    return sign * re;
}
int n, a[100005], b[100005], s[100005];
LL tot;
int tr[200005];
inline int lb(int x) {return x & (-x);}
inline void add(int x, int val)
{
    while(x <= (n << 1) + 1)
    {
        tr[x] += val;
        x += lb(x);
    }
}
inline int query(int x)
{
    int re = 0;
    while(x)
    {
        re += tr[x];
        x ^= lb(x);
    }
    return re;
}
inline bool chk(int mid)
{
    LL re = 0;
    FOR(i, 1, n)
        if(a[i] < s[mid]) b[i] = -1;
        else b[i] = 1;
    FOR(i, 1, n)
    {
        b[i] += b[i - 1];
        re += query(b[i] + n + 1);
        if(b[i] >= 0) re++;
        add(b[i] + n + 1, 1);
    }
    ROF(i, n, 1) add(b[i] + n + 1, -1);
    return re >= tot;
}
signed main()
{
    n = rd(); tot = 1ll * n * (n + 1) / 2ll; tot = (tot + 1) / 2ll;
    FOR(i, 1, n) a[i] = s[i] = rd();
    sort(s + 1, s + 1 + n);
    int l = 0, r = n + 1;
    while(l + 1 < r)
    {
        int mid = (l + r) >> 1;
        if(chk(mid)) l = mid;
        else r = mid;
    }
    printf("%d", s[l]);
    return 0;
}