题目描述：

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

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

 

　　样例解释：

　　[l,r]表示区间的值

　　[1]：3

　　[2]：1

　　[3]：2

　　[4]：4

　　[1,3]：2

　　[2,4]：2

　　第三大是2

输入：

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

输出：

　　一个数表示答案。

 

题解：

　　二分答案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] i与j奇偶性不同，BIT

 

#include
     
      using namespace std;const int N = 2e6+20, M = 1e5+10, mod = 1e9+7, inf = 2e9;typedef long long ll;int C[N][2],n;int a[N],b[N];ll k;void update(int x,int p) {    if(x==0) return ;    for(int i=x;i
      
       =t?1:0,b[i]+=b[i-1];    for(int i=1;i<=n;i++) b[i] = b[i]*2-i+M;    ll s=0;    update(M,0);    for(int i=1;i<=n;i++) {        s+=getsum(b[i],(i&1)^1);        update(b[i],(i&1));    }    return s;}int main(){    scanf("%d%lld",&n,&k);    int mx = 0;    for(int i=1;i<=n;i++) scanf("%d",&a[i]),mx = max(mx, a[i]);    int l=0,r=mx,ans=0;   // cout<
       
        <
        
         >1;        if(ask(mid)>=k) l=mid+1,ans=mid;        else r=mid-1;    }    printf("%d\n",ans);}