51nod 第K大区间2(二分+树状数组)

题目链接：

第K大区间2

基准时间限制：1.5 秒 空间限制：131072 KB 分值: 160

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

现给出n个数，求将所有长度为奇数的区间的值排序后，第K大的值为多少。

样例解释：

[l,r]表示区间的值
[1]：3
[2]：1
[3]：2
[4]：4
[1,3]：2
[2,4]：2

第三大是2

Input

第一行两个数n和k(1<=n<=100000,k<=奇数区间的数量)
第二行n个数，0<=每个数<2^31

Output

一个数表示答案。

Input示例

4 3
3 1 2 4

Output示例

2

题意：


思路：

二分答案t，统计中位数大于等于t的区间有多少个。

设a[i]为前i个数中有a[i]个数>=t，若奇数区间[l,r]的中位数>=t，则(a[r]-a[l-1])*2>r-l+1,即(a[r]*2-r)>(a[l-1]*2-l+1)。

设b[i]=a[i]*2-i，统计每个b[i]有多少个b[j]<b[i](j<i 且 j和i奇偶性不同)

总复杂度O(nlognlogn)

AC代码：

//#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
#define Riep(n) for(int i=1;i<=n;i++)
#define Riop(n) for(int i=0;i<n;i++)
#define Rjep(n) for(int j=1;j<=n;j++)
#define Rjop(n) for(int j=0;j<n;j++)
#define mst(ss,b) memset(ss,b,sizeof(ss));
typedef long long LL;
template<class T> void read(T&num) {
    char CH; bool F=false;
    for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());
    for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
    F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p) {
    if(!p) { puts("0"); return; }
    while(p) stk[++ tp] = p%10, p/=10;
    while(tp) putchar(stk[tp--] + '0');
    putchar('
');
}

const LL mod=1e9+7;
const double PI=acos(-1.0);
const LL inf=1e10;
const int N=1e5+15;

int n,k;
int a[N],b[N],sum[2][N];

int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int flag)
{
    while(x<=n)
    {
        sum[flag][x]++;
        x+=lowbit(x);
    }
}
int query(int x,int flag)
{
    int s=0;
    while(x>0)
    {
        s+=sum[flag][x];
        x-=lowbit(x);
    }
    return  s;
}



struct node
{
    int temp,pos,id;
}po[N];
int cmp1(node x,node y)
{
    if(x.temp==y.temp)return x.pos<y.pos;
    return x.temp<y.temp;
}
int cmp2(node x,node y)
{
    return x.pos<y.pos;
}
int check(LL x)
{
    mst(sum,0);
    Riep(n)
    {
        b[i]=b[i-1]+(a[i]>=x?1:0);
        po[i].temp=2*b[i]-i;
        po[i].pos=i;
    }
    sort(po+1,po+n+1,cmp1);
    Riep(n)po[i].id=i;
    sort(po+1,po+n+1,cmp2);
    LL ans=0;
    Riep(n)
    {
        if(po[i].temp>0&&i%2==1)ans++;//包括0的;
        ans=ans+query(po[i].id,i&1^1);
        update(po[i].id,i&1);
    }
    if(ans>=k)return 1;
    return 0;
}

int main()
{
      read(n);read(k);
      Riep(n)read(a[i]);
      LL l=1,r=inf;
      while(l<=r)
      {
          LL mid=(l+r)>>1;
          if(check(mid))l=mid+1;
          else r=mid-1;
      }
      print(l-1);
    return 0;
}