专栏文章

伪 Slope Trick

ccforrest
AT_abc383_g题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipkrgpn
此快照首次捕获于
2025/12/03 13:37
3 个月前
此快照最后确认于
2025/12/03 13:37
3 个月前
查看原文
对 这篇题解 的一点补充。
沿用记号，状态转移方程为
fi,j=max⁡{fi−1,j,fi−k,j−1+si−si−k}.f_{i,j} = \max\{f_{i-1,j},f_{i-k,j-1}+s_i-s_{i-k}\}.
现在归纳证明两点：
  1. fi,j−fi−k,j−1f_{i,j}-f_{i-k,j-1} 关于 jj 递减；
  2. fi,j−fi−1,jf_{i,j}-f_{i-1,j} 关于 jj 递增。
归纳起点是平凡的。假设命题对 i−1i-1 及之前的自然数都成立，现在证明它对 ii 也成立。直接验证即可。
首先，有
fi−1,j−fi−k,j−1=(fi−1,j−fi−1−k,j−1)−(fi−k,j−1−fi−1−k,j−1)f_{i-1,j}-f_{i-k,j-1}=(f_{i-1,j}-f_{i-1-k,j-1})-(f_{i-k,j-1}-f_{i-1-k,j-1})
关于 jj 递减，因为它的被减数关于 jj 递减，减数关于 jj 递增。
利用这个结论，有
fi,j−fi−k,j−1=max⁡{fi−1,j−fi−k,j−1,si−si−k}f_{i,j}-f_{i-k,j-1}=\max\{f_{i-1,j}-f_{i-k,j-1},s_i-s_{i-k}\}
关于 jj 递减，且
fi,j−fi−1,j=max⁡{0,si−si−k+fi−k,j−1−fi−1,j}f_{i,j}-f_{i-1,j}=\max\{0,s_i-s_{i-k}+f_{i-k,j-1}-f_{i-1,j}\}
关于 jj 递增。这就完成了归纳。
更进一步，有
fi,j−fi,j−1=fi,j−fi−k,j−1−∑ℓ=1k(fi−ℓ+1,j−1−fi−ℓ,j−1)f_{i,j}-f_{i,j-1} = f_{i,j}-f_{i-k,j-1}-\sum_{\ell=1}^k(f_{i-\ell+1,j-1}-f_{i-\ell,j-1})
关于 jj 递减，因为被减数递减，减数中的每一项都递增。这就说明 fi,jf_{i,j} 关于 jj 是凹函数。
同时，上面推导中的那个结论也说明对于任何 ii，都存在 pip_i 使得
fi,j={fi−1,j,j≤pi,fi−k,j−1+si−si−k,j>pi.f_{i,j} = \begin{cases}f_{i-1,j},&j\le p_i,\\ f_{i-k,j-1}+s_i-s_{i-k},&j>p_i.\end{cases}
虽然 这篇题解 求了个差分，凑成了 Slope Trick 的形式，但是似乎这个形式直接对原序列本身操作也是容易的，还不用维护平衡树中各项的和，直接二分完之后打个懒标记，再合并，然后直接输出最后的序列就好。
时间复杂度仍然是 O(nlog⁡2n)O(n\log^2n) 的。
CPP
/*  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 实现。区间加操作用标记永久化，不然会爆空间。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...