本文共 1701 字，大约阅读时间需要 5 分钟。

1685 第K大区间2

定义一个长度为奇数的区间的值为其所包含的的元素的中位数。中位数_百度百科

样例解释：

[l,r]表示区间的值

输入

第一行两个数n和k(1<=n<=100000,k<=奇数区间的数量)

输出

一个数表示答案。

输入样例

4 3

输出样例

2

代码实现

#include
   
    #define ll long longusing namespace std;const int maxn = 500000;int a[maxn], b[maxn], sum[maxn], n, k, ans, bit[2][maxn];int lowbit(int x) {
       return x & -x;}void update(int flag, int pos) {
       while (pos <= n * 2) {
           bit[flag][pos]++;        pos += lowbit(pos);    }}ll query(int flag, int pos) {
       ll res = 0;    while (pos) {
           res += bit[flag][pos];        pos -= lowbit(pos);    }    return res;}bool check(int mid) {
       memset(bit, 0, sizeof(bit));    memset(sum, 0, sizeof(sum));    ans = 0;    // 这样如果一个区间和大于0，这证明这个区间的中位数大于x，于是有sum[R] - sum[L-1] > 0    // 通过转化得到    // 2 * (sum[R] - sum[L-1]) > R-(L-1)    // 2 * sum[R] - R > 2 * sum[L - 1] - (L - 1)    // 问题转化成了区间1—n的前缀和中有多少正序对。    for (int i = 1; i <= n; i++) {
           sum[i] = sum[i - 1] + (a[i] >= mid);    }    for (int i = 0; i <= n; i++) {
           sum[i] = sum[i] * 2 - i + n;    }    update(0, n);    for (int i = 1; i <= n; i++) {
           // 对应奇偶数量的区间        ans += query(!(i & 1), sum[i] - 1);        update(i & 1, sum[i]);    }    return ans >= k;}int main() {
       cin >> n >> k;    for (int i = 1; i <= n; i++) {
           cin >> a[i];        b[i] = a[i];    }    sort(b + 1, b + 1 + n);    int l = 1, r = n;    while (l < r) {
           int mid = (l + r + 1) / 2;        if (check(b[mid])) {
               l = mid;        } else {
               r = mid - 1;        }    }    cout << b[l] << endl;    return 0;}
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/111501251 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！