【问题描述】
定义一个长度为奇数的区间的值为其所包含的的元素的中位数。
现给出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#include #include #include using namespace std;typedef long long ll;ll n, k, a[100010], b[100010], l, r, ans, c[2][300010];long long anss;long long query(ll x, ll id){ long long res = 0; while (x) { res += c[id][x]; x -= x & (-x); } return res;}void add(ll x, ll id){ while (x <= 200100) { c[id][x]++; x += x & (-x); }}ll cal(ll p){ b[0] = 0; memset(c, 0, sizeof(c)); for (int i = 1; i <= n; i++) { b[i] = b[i - 1]; if (a[i] >= p) b[i]++; } for (int i = 0; i <= n; i++) b[i] = 2 * b[i] - i + 100010; anss = 0; for (int i = 0; i <= n; i++) { anss += query(b[i] - 1, ((i & 1) + 1) % 2); add(b[i], i & 1); } return anss;}int main(){ scanf("%lld%lld", &n, &k); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); r = max(r, a[i]); } l = 0; while (l <= r) { ll mid = (l + r) >> 1; if (cal(mid) >= k) { ans = mid; l = mid + 1; } else r = mid - 1; } printf("%lld\n", ans); return 0;}