伪 Slope Trick

cforrest · 2025-04-18 10:55:06 · 题解

对 这篇题解 的一点补充。

沿用记号，状态转移方程为

现在归纳证明两点：

归纳起点是平凡的。假设命题对 i-1 及之前的自然数都成立，现在证明它对 i 也成立。直接验证即可。

首先，有

关于 j 递减，因为它的被减数关于 j 递减，减数关于 j 递增。

利用这个结论，有

关于 j 递减，且

关于 j 递增。这就完成了归纳。

更进一步，有

关于 j 递减，因为被减数递减，减数中的每一项都递增。这就说明 f_{i,j} 关于 j 是凹函数。

同时，上面推导中的那个结论也说明对于任何 i，都存在 p_i 使得

虽然 这篇题解 求了个差分，凑成了 Slope Trick 的形式，但是似乎这个形式直接对原序列本身操作也是容易的，还不用维护平衡树中各项的和，直接二分完之后打个懒标记，再合并，然后直接输出最后的序列就好。

时间复杂度仍然是 O(n\log^2n) 的。

/*  headers */

class WBLT {
    struct Node {
        int ch[2], sz;
        long long lz;
        Node() : ch{}, sz{}, lz{} {}
    };

    static constexpr int DELTA = 3;
    static constexpr long long inf = 0x3f3f3f3f3f3f3f3f;

    int id;
    std::vector<int> rt;
    std::vector<Node> node;    

#define getter(var) \
    auto var(int x) const { return node[x].var; } \
    auto& var(int x) { return node[x].var; }

    getter(sz)
    getter(lz)

#undef getter

    auto& ch(int x, int i) { return node[x].ch[i]; }
    auto ch(int x, int i) const { return node[x].ch[i]; }

    int new_node() { return ++id; }
    void del_node(int& x) { /* pass */ }

    void copy_node(int& x) {
        int y = new_node();
        node[y] = node[x];
        x = y;
    }

    int new_leaf(long long v) {
        int x = new_node();
        lz(x) = v;
        sz(x) = 1;
        return x;
    }

    int new_tree(int x, int y) {
        int z = new_node();
        ch(z, 0) = x;
        ch(z, 1) = y;
        push_up(z);
        return z;
    }

    std::pair<int, int> cut_tree(int& x) {
        int y = ch(x, 0);
        int z = ch(x, 1);
        del_node(x);
        return { y, z };
    }

    void lazy_add(int& x, long long v) {
        if (!x) return;
        copy_node(x);
        lz(x) += v;
    }

    void push_up(int x) {
        sz(x) = sz(ch(x, 0)) + sz(ch(x, 1));
    }

    void push_down(int& x) {
        if (lz(x)) {
            copy_node(x);
            lazy_add(ch(x, 0), lz(x));
            lazy_add(ch(x, 1), lz(x));
            lz(x) = 0;
        }
    }

    int merge(int x, int y) {
        if (!x || !y) return x | y;
        if (sz(x) > sz(y) * DELTA) {
            push_down(x);
            auto [a, b] = cut_tree(x);
            if (sz(a) * DELTA >= (sz(b) + sz(y))) {
                return merge(a, merge(b, y));
            } else {
                push_down(b);
                auto [c, d] = cut_tree(b);
                return merge(merge(a, c), merge(d, y));
            }
        } else if (sz(y) > sz(x) * DELTA) {
            push_down(y);
            auto [a, b] = cut_tree(y);
            if (sz(b) * DELTA >= (sz(a) + sz(x))) {
                return merge(merge(x, a), b);
            } else {
                push_down(a);
                auto [c, d] = cut_tree(a);
                return merge(merge(x, c), merge(d, b));
            }
        } else {
            return new_tree(x, y);
        }        
    }

    long long kth_elem(int x, int k, long long v) {
        if (k <= 0 || k > sz(x)) return -inf;
        if (sz(x) == 1) return lz(x) + v;
        return k <= sz(ch(x, 0))
            ? kth_elem(ch(x, 0), k, v + lz(x))
            : kth_elem(ch(x, 1), k - sz(ch(x, 0)), v + lz(x));
    }

    std::pair<int, int> split(int x, int k) {
        if (!x) return { 0, 0 };
        if (k <= 0) return { 0, x };
        if (k >= sz(x)) return { x, 0 };
        push_down(x);
        auto [a, b] = cut_tree(x);
        if (k <= sz(a)) {
            auto [ll, rr] = split(a, k);
            return { ll, merge(rr, b) };
        } else {
            auto [ll, rr] = split(b, k - sz(a));
            return { merge(a, ll), rr };
        }
    }

    void print(int x, long long v) {
        if (!x) return;
        print(ch(x, 0), v + lz(x));
        if (sz(x) == 1) std::cout << (v + lz(x)) << ' ';
        print(ch(x, 1), v + lz(x));
    }

public:
    WBLT(int n) : id(0), rt(n), node(n << 1) {
        rt[0] = new_leaf(0);
    }

    void modify(int i, int k, long long v) {
        if (i < k) {
            rt[i] = rt[0];
            return;
        }
        int ll = 1, rr = sz(rt[i - 1]);
        int p = 0;
        while (ll <= rr) {
            int mm = (ll + rr) / 2;
            if (kth_elem(rt[i - 1], mm, 0) >= kth_elem(rt[i - k], mm - 1, 0) + v) {
                p = mm;
                ll = mm + 1; 
            } else {
                rr = mm - 1;
            }
        }
        auto [l, r] = split(rt[i - 1], p);
        rt[i] = l;
        std::tie(l, r) = split(rt[i - k], p - 1);
        lazy_add(r, v);
        rt[i] = merge(rt[i], r);
    }

    void print(int i) {
        auto [ll, rr] = split(rt[i], 1);
        print(rr, 0);
        std::cout << '\n';
    }
};

int main() {
    int n, k;
    std::cin >> n >> k;
    std::vector<long long> s(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> s[i];
        s[i] += s[i - 1];
    }
    WBLT dp(2e7);
    for (int i = 1; i <= n; ++i) {
        dp.modify(i, k, i >= k ? s[i] - s[i - k] : 0);
    }
    dp.print(n);
    return 0;
}

因为全是区间复制，所以用了 WBLT 实现。区间加操作用标记永久化，不然会爆空间。