po167_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub potato167/po167_library

:heavy_check_mark: test/algorithm/monge_1.test.cpp

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/952"

#include "../../algorithm/monge_d_edge_shortest_path.hpp"
#include "../../algorithm/monge_k_edge_shortest_path.hpp"
#include <iostream>
#include <vector>

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;
    std::vector<long long> S(N + 1);
    for (int i = 0; i < N; i++){
        std::cin >> S[i + 1];
        S[i + 1] += S[i];
    }

    auto cost = [&](int i, int j){
        long long s = S[j - 1] - S[i];
        return s * s;
    };
    auto ans = po167::monge_k_edge_shortest_path<long long>(N + 1, N, cost);

    // Selected edge counts are computed by the fixed-D function.
    std::vector<bool> check(N + 1);
    for (int t = 0; t < 32; t++) check[1 + (N - 1) * t / 31] = true;
    if (N >= 2) check[2] = check[N - 1] = true;
    for (int d = 1; d <= N; d++){
        if (check[d]) ans[d] = po167::monge_d_edge_shortest_path(N + 1, d, cost);
    }
    for (int k = 1; k <= N; k++){
        std::cout << ans[N + 1 - k] << "\n";
    }
}
#line 1 "test/algorithm/monge_1.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/952"

#line 2 "algorithm/monge_d_edge_shortest_path.hpp"
// po167 Monge library v2 (2026-10-21)
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
#line 2 "algorithm/larsch.hpp"
// po167 Monge library v2 (2026-10-21)
#line 6 "algorithm/larsch.hpp"

namespace po167 {
namespace detail {

// A[r][c] = value(r,c), 0 <= c <= r < n: Monge.
// r-th next_argmin() = min argmin_{0 <= c <= r} A[r][c].
// O(n) total time, O(n) space.
// https://noshi91.github.io/Library/algorithm/larsch.cpp.html (CC0)
template <class F>
class Larsch {
    struct Level {
        int n, row = 0, state = 0, size = 0;
        std::vector<int> column;
        Level(int n_, bool base) : n(n_), column(base ? 0 : n_) {}
    };
    F value;
    std::vector<Level> levels;

    int next_argmin(int depth) {
        auto& a = levels[depth];
        int row = a.row++, r = ((row + 1) << depth) - 1;
        auto column = [&](int j) { return depth ? a.column[j] : j; };
        int best = column(a.state);
        if (row & 1) {
            int last = column(row);
            return value(r, last) < value(r, best) ? last : best;
        }
        int bound;
        if (row + 1 == a.n) {
            bound = column(a.n - 1);
        } else {
            auto& b = levels[depth + 1];
            for (int j = (row ? row - 1 : 0); j <= row; ++j) {
                int c = column(j);
                while (b.size > row / 2) {
                    int q = (b.size << (depth + 1)) - 1;
                    if (!(value(q, c) < value(q, b.column[b.size - 1]))) break;
                    --b.size;
                }
                if (b.size < b.n) b.column[b.size++] = c;
            }
            bound = next_argmin(depth + 1);
        }
        if (best != bound) {
            auto best_value = value(r, best);
            do {
                int c = column(++a.state);
                auto candidate = value(r, c);
                if (candidate < best_value) best_value = candidate, best = c;
            } while (column(a.state) != bound);
        }
        return best;
    }

public:
    // A[r][c] = value_(r,c), 0 <= c <= r < n; next row = 0.
    Larsch(int n, F value_) : value(std::move(value_)) {
        assert(n >= 0);
        for (int size = n; size; size /= 2) levels.emplace_back(size, levels.empty());
    }

    // return min argmin_{0 <= c <= r} A[r][c], then r <- r+1.
    int next_argmin() {
        assert(!levels.empty() && levels[0].row < levels[0].n);
        return next_argmin(0);
    }

    // r <- 0; A may be changed before the next sequence of queries.
    void reset() {
        for (auto& a : levels) a.row = a.state = a.size = 0;
    }
};

}  // namespace detail
}  // namespace po167
#line 8 "algorithm/monge_d_edge_shortest_path.hpp"

namespace po167 {

// f(a,c)+f(b,d) <= f(a,d)+f(b,c) (0 <= a < b < c < d <= n).
// return min_{0=v_0 < v_1 < ... < v_d=n} sum_{t=1}^d f(v_{t-1},v_t).
// 1 <= d <= n; f(i,j) and the answer must fit in long long. Internal type: __int128_t.
// O(n log(W+2)) time, O(n) space; W is the internally computed penalty range.
template <class F>
long long monge_d_edge_shortest_path(int n, int d, const F& f) {
    using T = __int128_t;
    const T inf = T(1) << 120;
    assert(1 <= d && d <= n);
    if (d == 1) return f(0, n);
    if (d == n) {
        T total = 0;
        for (int i = 0; i < n; ++i) total += T(f(i, i + 1));
        return (long long)total;
    }

    // C[1], C[2], C[n], C[n]-C[n-1].
    T one = f(0, n), two = inf, total = f(0, 1);
    T previous = total, last_diff = -inf;
    for (int i = 1; i < n; ++i) {
        T next = f(i, i + 1);
        total += next;
        two = std::min(two, T(f(0, i)) + T(f(i, n)));
        last_diff = std::max(last_diff, previous + next - T(f(i - 1, i + 1)));
        previous = next;
    }
    if (d == 2) return (long long)two;
    if (d == n - 1) return (long long)(total - last_diff);

    std::vector<T> dp(n + 1);
    std::vector<int> parent(n + 1);
    auto value = [&](int row, int col) { return dp[col] + T(f(col, row + 1)); };
    detail::Larsch<decltype(value)> solver(n, value);
    auto solve = [&](T penalty) {
        solver.reset();
        dp[0] = penalty;
        for (int v = 1; v <= n; ++v) {
            int p = parent[v] = solver.next_argmin();
            dp[v] = dp[p] + T(f(p, v)) + penalty;
        }
        int count = 0;
        for (int v = n; v; v = parent[v]) ++count;
        return std::pair<T, int>(dp[n] - penalty, count);
    };

    T lo = -last_diff, hi = one - two;
    assert(lo <= hi);
    T answer = std::max(total + T(n - d) * lo, one + T(1 - d) * hi);
    T left_cost = total, right_cost = one;
    int left_count = n, right_count = 1;
    ++lo;
    --hi;
    bool bisect = false;
    while (lo <= hi) {
        T width = hi - lo, x = lo + width / 2;
        if (!bisect) {
            // left_cost+left_count*x = right_cost+right_count*x.
            T a = right_cost - left_cost, b = left_count - right_count;
            x = std::clamp(a / b - (a % b < 0), lo, hi);
        }
        auto [cost, count] = solve(x);
        answer = std::max(answer, cost - T(d) * x);
        if (count == d) break;
        if (count > d) {
            lo = x + 1;
            left_cost = cost - T(count) * x;
            left_count = count;
        } else {
            hi = x - 1;
            right_cost = cost - T(count) * x;
            right_count = count;
        }
        bisect = 2 * (hi - lo) > width;
    }
    return (long long)answer;
}

// return monge_d_edge_shortest_path(n,d,f); upper is unused (compatibility overload).
template <class F>
long long monge_d_edge_shortest_path(int n, int d, long long, const F& f) {
    return monge_d_edge_shortest_path(n, d, f);
}

}  // namespace po167
#line 2 "algorithm/monge_k_edge_shortest_path.hpp"
// po167 Monge library v2 (2026-10-21)
#line 3 "algorithm/smawk.hpp"
#include <numeric>
namespace po167{
// return argmax
// 
// https://noshi91.github.io/Library/algorithm/smawk.cpp
template<class S> std::vector<int> smawk(int N, int M, S select){
    auto f = [&](auto self, std::vector<int> p,std::vector<int> q) -> std::vector<int> {
        // reduce
        std::vector<int> n_q;
        n_q.reserve(p.size());
        int k = -1;
        for(auto x:q){
            while(!n_q.empty()){
                if(!select(p[k], n_q.back(), x)) break;
                n_q.pop_back();
                k--;
            }
            if (k + 1 != (int)p.size()){
                n_q.push_back(x);
                k++;
            }
        }
        std::swap(n_q, q);

        int n = p.size();
        int m = q.size();
        
        // recursive
        if (n == 1){
            return q;
        }
        std::vector<int> n_p;
        n_p.reserve(n / 2);

        for (int i = 1; i < n; i += 2){
            n_p.push_back(p[i]);
        }
        
        auto fr = self(self, n_p, q);
        // interpolate
        std::vector<int> ans(n);
        int l = 0, r = 0;
        
        for (int i = 0; i < n; i++){
            if(i & 1){
                ans[i] = fr[i / 2];
                l = r;
            } else {
                if (i + 1 != n) {
                    while (q[r] != fr[i / 2]) r++;
                } else {
                    r = m - 1;
                }
                ans[i] = q[l];
                for (int j = l + 1; j <= r; j++){
                    if(select(p[i], ans[i], q[j])){
                        ans[i] = q[j];
                    }
                }
            }
        }
        return ans;
    };
    std::vector<int> P(N), Q(M);
    std::iota(P.begin(), P.end(), 0);
    std::iota(Q.begin(), Q.end(), 0);
    return f(f, P, Q);
}
}
#line 6 "algorithm/monge_k_edge_shortest_path.hpp"

namespace po167 {

// f: {(i,j) | 0 <= i < j <= n} -> long long, 0 <= k <= n.
// f(a,c) + f(b,d) <= f(a,d) + f(b,c)  (a < b < c < d).
// ans[d] = min_{0 = v_0 < ... < v_d = n} sum_{t=1}^d f(v_{t-1},v_t), 1 <= d <= k.
// ans[0] は未使用。各 ans[d] は long long、全 DP 値・候補値は T に収まること。
// f が O(1) のとき、時間 O(nk)、追加メモリ O(n)。
template <class T = __int128_t, class F>
std::vector<long long> monge_k_edge_shortest_path(int n, int k, const F& f) {
    assert(0 <= k && k <= n);
    std::vector<long long> answer(k + 1);
    if (k == 0) return answer;
    answer[1] = f(0, n);
    if (k == 1) return answer;

    std::vector<T> prev(n + 1), next(n + 1);
    for (int j = 1; j < n; ++j) prev[j] = T(f(0, j));
    prev[n] = T(answer[1]);
    for (int d = 2; d <= k; ++d) {
        int size = n - d + 1;
        auto argmin = po167::smawk(size, size, [&](int r, int a, int b) {
            int j = r + d, i = a + d - 1, h = b + d - 1;
            return h < j && prev[h] + T(f(h, j)) < prev[i] + T(f(i, j));
        });
        for (int j = d; j <= n; ++j) {
            int i = argmin[j - d] + d - 1;
            next[j] = prev[i] + T(f(i, j));
        }
        answer[d] = (long long)next[n];
        prev.swap(next);
    }
    return answer;
}

}  // namespace po167
#line 5 "test/algorithm/monge_1.test.cpp"
#include <iostream>
#line 7 "test/algorithm/monge_1.test.cpp"

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;
    std::vector<long long> S(N + 1);
    for (int i = 0; i < N; i++){
        std::cin >> S[i + 1];
        S[i + 1] += S[i];
    }

    auto cost = [&](int i, int j){
        long long s = S[j - 1] - S[i];
        return s * s;
    };
    auto ans = po167::monge_k_edge_shortest_path<long long>(N + 1, N, cost);

    // Selected edge counts are computed by the fixed-D function.
    std::vector<bool> check(N + 1);
    for (int t = 0; t < 32; t++) check[1 + (N - 1) * t / 31] = true;
    if (N >= 2) check[2] = check[N - 1] = true;
    for (int d = 1; d <= N; d++){
        if (check[d]) ans[d] = po167::monge_d_edge_shortest_path(N + 1, d, cost);
    }
    for (int k = 1; k <= N; k++){
        std::cout << ans[N + 1 - k] << "\n";
    }
}
Back to top page