【问题描述】
定义一个长度为奇数的区间的值为其所包含的的元素的中位数。
现给出n个数,求将所有长度为奇数的区间的值排序后,第K大的值为多少。
【输入】
输入文件名为kth.in。
第一行两个数n和k
第二行,n个数。(0<=每个数<231)
【输出】
输出文件名为kth.out。
一个数表示答案。
【输入输出样例】
kth.in |
kth.out |
4 3 3 1 2 4 |
2 |
【样例解释】
[l,r]表示区间l~r的值
[1,1]:3
[2,2]:1
[3,3]:2
[4,4]:4
[1,3]:2
[2,4]:2
【数据说明】
对于30%的数据,1<=n<=100;
对于60%的数据,1<=n<=300
对于80%的数据,1<=n<=1000
对于100%的数据,1<=n<=100000, k<=奇数区间的数
分析:有点难想的一道题.
看到第k大,就应该想到要二分.二分x,接下来的任务就是找有多少个区间的值>=x.既然是中位数>=x,那么比x大的数在区间中肯定占了一半以上的数量,那么开一个数组sum[i]表示1~i中有多少个数>=x.一个区间只有2*(sum[r] – sum[l – 1]) > r – (l – 1).接下来就是常见的套路了,把结构相同的放在一起:2*sum[r] – r > 2*sum[l – 1] – (l – 1),换个元,另b[i] = 2*sum[i] – i,问题就转化成了有多少个j满足j < i && b[j] < b[i],树状数组维护一遍就可以了.由于区间长度为奇数,所以要开两个树状数组分别记录奇数和偶数的答案.
第k小/大用二分,式子一定要变形,相同结构放一起,换元之后再求解.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long ll;ll n, k, a[], b[], l, r, ans, c[][];
long long anss;long long query(ll x, ll id)
{
long long res = ;
while (x)
{
res += c[id][x];
x -= x & (-x);
}
return res;
}void add(ll x, ll id)
{
while (x <= )
{
c[id][x]++;
x += x & (-x);
}
}ll cal(ll p)
{
b[] = ;
memset(c, , sizeof(c));
for (int i = ; i <= n; i++)
{
b[i] = b[i - ];
if (a[i] >= p)
b[i]++;
}
for (int i = ; i <= n; i++)
b[i] = * b[i] - i + ;
anss = ;
for (int i = ; i <= n; i++)
{
anss += query(b[i] - , ((i & ) + ) % );
add(b[i], i & );
}
return anss;
}int main()
{
scanf("%lld%lld", &n, &k);
for (int i = ; i <= n; i++)
{
scanf("%lld", &a[i]);
r = max(r, a[i]);
}
l = ;
while (l <= r)
{
ll mid = (l + r) >> ;
if (cal(mid) >= k)
{
ans = mid;
l = mid + ;
}
else
r = mid - ;
}
printf("%lld\n", ans); return ;
}