题目描述：
定义一个长度为奇数的区间的值为其所包含的的元素的中位数。现给出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
树状数组大小注意：1—n中不光有n个区间！
用树状数组求逆序对。为什么不用归并，因为题目要求的是奇区间。
所以两棵BIT，一棵记录奇区间，一个记录偶区间。
为什么求逆序对：
考虑这个题，求第k大，我们想到可以二分。如何判断二分？
不妨我们设二分x这个值前面有多少比他大的，那么对于一个区间L—R，大于等于x设为1，小于x设为-1
求一下前缀和。这样如果一个区间和大于0，这证明这个区间的中位数大于x，于是有sum[R] - sum[L-1] > 0，把这个式子转化一下：
因为上面式子>0就说明比他大的超过一半区间。
2 * (sum[R] - sum[L-1]) > R-(L-1)
2 * sum[R] - R > 2 * sum[L-1]-(L-1)
于是问题转化成了区间1—n的前缀和中有多少正序对。
不是很好理解，有点小绕。
原题作者题解为这样：
二分答案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)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll int
using namespace std;
const int maxn = 500000;
int n, k, ans, a[maxn], b[maxn], s[maxn], sum[maxn];
int 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)
{
//cout<<mid<<"qwq\n";
memset(bit, 0, sizeof(bit));
memset(sum, 0, sizeof(sum));
ans = 0;
for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + (a[i] >= mid);
for(int i = 1; i <= n; i++) sum[i] = 2*sum[i] - i+n;
update(0, n);
for(int i = 1; i <= n; i++)
{
ans += query(!(i&1), sum[i]-1);
update(i&1,sum[i]);
}
//for(int i = 1; i <= n; i++) cout<<bit[0][i]<<" ";
//cout<<"ans:"<<ans<<endl;
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) >> 1;
//cout<<mid<<"qnq\n";
if(check(b[mid])) l = mid;
else r = mid - 1;
}
cout<<b[l];
return 0;
}