第2题

给定一个整数序列 $a_1,a_2,\ldots,a_n$，对该序列的所有子区间，分别算出它们的中位数，并且将这些中位数组成一个新序列，输出这个新序列的中位数。

所谓一个序列的中位数，就是将这个序列排序后，排名在最中间的数字，如果序列的长度是偶数，规定中位数是排名最居中的两个数之中偏大的数。

#include<iostream>
const int maxn = 1000000;
int a[maxn];
int b[maxn];
int s[maxn + 1];
int n;
long long total;

long long merge(int begin, int mid, int end) {
    int buffer[end - begin];
    auto i = begin;
    auto j = mid;
    auto k = 0;
    long long sum = 0;
    while (i < mid and j < end) {
        if (s[i] <= s[j]) {
            buffer[k++] = s[i++];
            sum += ____(1)____;
        }
        else {
            buffer[k++] = s[j++];
        }
    }
    while (i < mid) buffer[k++] = s[i++];
    while (j < end) buffer[k++] = s[j++];
    for (int x = begin, k = 0; x < end; ++x, ++k)
        s[x] = buffer[k];
    return sum;
}
long long merge_sort(int begin, int end) {
    auto length = end - begin;
    if (____(2)____) return 0;
    auto mid = begin + length / 2;
    auto front = merge_sort(begin, mid);
    auto back = merge_sort(mid, end);
    auto cross = merge(begin, mid, end);
    return ____(3)____;
}

bool predicate(int key) {
    for (int i = 0; i < n; ++i) {
        if (____(4)____)
            b[i] = 1;
        else
            b[i] = -1;
        s[i+1] = s[i] + b[i];
    }
    long long num = ____(5)____;
    return ____(6)____;
}
int main() {
    std::cin >> n;
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    total = (long long)n * (n + 1) / 2;

    int begin = 0;
    int end = 1000000001;
    while (true) {
        int length = ____(7)____;
        if (length == 1) break;
        auto mid = ____(8)____;
        if (predicate(mid))
            begin = mid;
        else
            end = mid;
    }
    std::cout << ____(9)____ << "\n";
}

(4)(5) 处应填（ ）。

{{ select(1) }}

• a[i] > key，merge_sort(0, n)
• a[i] < key，merge_sort(0, n + 1)
• a[i] < key，merge_sort(0, n)
• a[i] > key，merge_sort(0, n + 1)