题目描述：
定义一个长度为奇数的区间的值为其所包含的的元素的中位数。
现给出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<bits/stdc++.h>
using namespace std;
const int N = 2e6+, M = 1e5+, mod = 1e9+, inf = 2e9;
typedef long long ll; int C[N][],n;
int a[N],b[N];
ll k;
void update(int x,int p) {
if(x==) return ;
for(int i=x;i<N;i+=i&(-i)) C[i][p]+=;
}
int getsum(int x,int p) {
int s = ;
for(int i=x;i;i-=i&(-i)) s+=C[i][p];
return s;
}
ll ask(int t)
{
memset(C,,sizeof(C));
b[]=;
for(int i=;i<=n;i++) b[i]=a[i]>=t?:,b[i]+=b[i-];
for(int i=;i<=n;i++) b[i] = b[i]*-i+M;
ll s=;
update(M,);
for(int i=;i<=n;i++) {
s+=getsum(b[i],(i&)^);
update(b[i],(i&));
}
return s;
}
int main(){
scanf("%d%lld",&n,&k);
int mx = ;
for(int i=;i<=n;i++) scanf("%d",&a[i]),mx = max(mx, a[i]);
int l=,r=mx,ans=;
// cout<<ask(2)<<endl;//return 0;
while(l<=r) {
int mid = (l+r)>>;
if(ask(mid)>=k) l=mid+,ans=mid;
else r=mid-;
}
printf("%d\n",ans);
}