ACM模版

描述

题解

二分 + 树状数组。

二分枚举答案，判断中位数大于等于当前答案的个数是否足够 k 个，至于怎么判断，我们需要借助树状数组。首先我们可以通过前缀的方法获取前 i 个数字有几个大于 m 的，这里的 m 是我们枚举的答案，然后我们可以知道，我们需要求得是 sum[j]−sum[i−1]>j−i2,j≠i 的个数，转化为更容易观察的样式 2∗sum[j]−j>2∗sum[i]−i,j≠i ，所以我们可以设 c[i]=2∗sum[i]−i 。为了避免出现负数，我们可以整体进行偏移 n <script type="math/tex" id="MathJax-Element-721">n</script>，然后我们就可以在合适的时间内计数和查找。

十分有趣的一个题，注意奇偶性的问题，这也是为什么要使用两棵树状数组的原因，这样就能保证每次查找的区间都是奇数个，就这样，没什么了。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

int n;
ll k;
int a[MAXN];
int b[MAXN];
int c[MAXN];
int sum[MAXN];
int tree[2][MAXN * 3];

void add(int rt, int x, int y = 1)
{
    if (x <= 0)
    {
        return ;
    }
    int tmp = 3 * n;
    for (; x <= tmp; x += x & -x)
    {
        tree[rt][x] += y;
    }
}

int get_sum(int rt, int x)
{
    if (x <= 0)
    {
        return 0;
    }
    int ret = 0;
    for (; x; x -= x & -x)
    {
        ret += tree[rt][x];
    }
    return ret;
}

ll check(int x)
{
    ll ret = 0;
    memset(tree, 0, sizeof(tree));
    for (int i = 1; i <= n; i++)
    {
        sum[i] = sum[i - 1] + (a[i] >= x);
        c[i] = 2 * sum[i] - i + n;  // +n 是偏移一下，以防负数
    }

    add(0, n);
    for (int i = 1; i <= n; i++)
    {
        add(i & 1, c[i]);
        ret += get_sum((i + 1) & 1, c[i] - 1);
    }
    return ret;
}

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int main()
{
    scan_d(n), scan_d(k);
    for (int i = 1; i <= n; i++)
    {
        scan_d(a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);

    int l = 1, r = n + 1, m;
    while (l + 1 < r)
    {
        m = (l + r) >> 1;
        if (check(b[m]) >= k)
        {
            l = m;
        }
        else
        {
            r = m;
        }
    }

    printf("%d\n", b[l]);

    return 0;
}