题面：
Description
实验室的仓库中有n堆的财宝，第i堆财宝有ai个，且价值均为i 。面对如此多的财宝，实验室的管理员每天都会来统计这些财宝的中位数是什么。 但是每天实验室都会有开销，每天的开销为第 kk 大的财宝，聪明的你能帮助管理员统计每天结束后的财宝吗？

Input
第一行为一个n，表示有n堆财宝。第二行有n个数，ai表示第i堆财宝的数量。第三行为一个q，表示一共有q天.而后一共q行，每行一个k，表示每一天的开销为剩余财宝的第k大的财宝。

Output
一共输出q 行，表示第i天后财宝的中位数。结果保留1位小数。

Sample Input 1 

5
1 2 1 2 1
2
2
1
Sample Output 1

2.5
2.0

Hint
q < 1000, n < 1000000, ai < 1000

保证k小于等于当前剩余财宝的总量。
若剩余偶数个财宝，中位数为中间两个取算数平均值。

方法一：前缀和 + 二分查找

#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

int n, sum;
int a[N], s[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%d", &a[i]);
        sum += a[i];
        s[i] = s[i - 1] + a[i];
    }

    int q;
    scanf("%d", &q);
    while (q -- )
    {
        int k;
        scanf("%d", &k);
        int i = lower_bound(s + 1, s + n + 1, sum - k + 1) - s;

        while (i <= n)
        {
            s[i ++ ] --; 
        }
        sum -- ;

        if (sum % 2 == 1) 
        {
            double f1 = upper_bound(s + 1, s + n + 1, sum / 2) - s;
            printf("%.1f\n", f1);
        }
        else
        {
            double f1 = upper_bound(s + 1, s + n, sum / 2) - s, f2 = lower_bound(s + 1, s + n, sum / 2) - s;
            printf("%.1f\n", (f1 + f2) / 2); 
        }
    }
}

方法二：线段树

#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

int n, q;
int w[N];
struct Node
{
    int l, r;
    int sum;
}tr[N * 4];


void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[l]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);

        pushup(u);
    }
}

void modify(int u, int x)
{
    if (tr[u].l == tr[u].r) tr[u].sum -- ;
    else
    {
        if (x <= tr[u << 1].sum) modify(u << 1, x);
        else modify(u << 1 | 1, x - tr[u << 1].sum);

        pushup(u);
    }
}

double query(int u, int k)
{
    if (tr[u].l == tr[u].r) return tr[u].l;

    if (k <= tr[u << 1].sum) return query(u << 1, k);
    else return query(u << 1 | 1, k - tr[u << 1].sum);
}


int main()
{
    scanf("%d", &n);
    int sum = 0;
    for (int i = n; i >= 1; i -- ) 
    {
        scanf("%d", &w[i]);
        sum += w[i]; 
    } 

    build(1, 1, n);

    scanf("%d", &q);
    while (q -- )
    {
        int k;
        scanf("%d", &k);

        modify(1, k);

        sum -- ;
        if (sum % 2 == 1) printf("%.1f\n", n + 1- query(1, sum / 2 + 1));
        else printf("%.1f\n", n + 1 - (query(1, sum / 2) + query(1, sum / 2 + 1)) / 2);
    }

    return 0;
}