题目链接：LOJ 6620

已知两个 $n$ 维实向量 $\vec{a} = (a_{1}, a_{2}, \ldots, a_{n}), \vec{b} = (b_{1}, b_{2}, \ldots, b_{n})$，定义 $n$ 个定义域为 $\mathbb{R}$ 函数 $f_{1}, f_{2}, \ldots, f_{n}$：

$$ f_k(x) = \sum_{i = 1} ^ {k} \lvert a_i x + b_i \rvert \quad (k = 1, 2, \ldots, n) $$

现在，对于每个 $k = 1, 2, \ldots, n$，试求 $f_k$ 在 $\mathbb{R}$ 上的最小值。可以证明最小值一定存在。

数据范围：$1 \le n \le 5 \times 10 ^ 5$，$\lvert a_i \rvert, \lvert b_i \rvert < 10 ^ 5$。

Solution

$f_k(x)$ 的最小值等价于求 $-\frac{b_1}{a_1}, -\frac{b_2}{a_2}, \ldots, -\frac{b_k}{a_k}$ 的带权中位数，对向量按照 $-\frac{b_i}{a_i}$ 排序后在线段树上单点加 $a_i$ 并二分即可。

时间复杂度：$\mathcal O(n \log n)$。

Code

#include <bits/stdc++.h>
typedef long long int64;

const int N = 5e5;
int n, a[N + 5], b[N + 5], id[N + 5], pos[N + 5];

struct Segment {
    #define ls u << 1
    #define rs u << 1 | 1
    #define lson ls, l, mid
    #define rson rs, mid + 1, r
    int64 sum[2][1 << 20 | 1];
    void modify(int x, int w, int o, int u, int l, int r) {
        if (l == r) {
            sum[o][u] += w;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) {
            modify(x, w, o, lson);
        } else {
            modify(x, w, o, rson);
        }
        sum[o][u] = sum[o][ls] + sum[o][rs];
    }
    int64 query(int x, int y, int o, int u, int l, int r) {
        if (x == l && r == y) {
            return sum[o][u];
        }
        int mid = (l + r) >> 1;
        if (y <= mid) {
            return query(x, y, o, lson);
        } else if (x > mid) {
            return query(x, y, o, rson);
        } else {
            return query(x, mid, o, lson) + query(mid + 1, y, o, rson);
        }
    }
    int find(int64 w, int u, int l, int r) {
        if (l == r) {
            return l;
        }
        int mid = (l + r) >> 1;
        if (sum[0][ls] >= w) {
            return find(w, lson);
        } else {
            return find(w - sum[0][ls], rson);
        }
    }
    inline int find(int64 w) {
        return find(w, 1, 1, n);
    }
    inline void modify(int x, int w, int o) {
        modify(x, w, o, 1, 1, n);
    }
    inline int64 query(int l, int r, int o) {
        return l > r ? 0 : query(l, r, o, 1, 1, n);
    }
    #undef ls
    #undef rs
    #undef lson
    #undef rson
} T;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
        if (a[i] < 0) {
            a[i] = -a[i];
            b[i] = -b[i];
        }
    }
    std::iota(id + 1, id + n + 1, 1);
    std::sort(id + 1, id + n + 1, [](int x, int y) {
        return (int64)b[x] * a[y] > (int64)b[y] * a[x];
    });
    for (int i = 1; i <= n; i++) {
        pos[id[i]] = i;
    }
    int64 sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += a[i];
        T.modify(pos[i], a[i], 0);
        T.modify(pos[i], b[i], 1);
        int p = T.find((sum + 1) / 2);
        double x = 1.0 * -b[id[p]] / a[id[p]];
        printf("%.10lf\n", (T.query(1, p, 0) - T.query(p + 1, n, 0)) * x + T.query(1, p, 1) - T.query(p + 1, n, 1));
    }
    return 0;
}