2022.10.12-D 中位数

题意：

我们记一个长度为 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;
}