yukicoder No.2546 Many Arithmetic Sequences
(tests/yukicoder/yukicoder_2546_cht_general_and_M_convex_priority_queue.test.cpp)

View this file on GitHub
Last update: 2026-11-12 11:56:29+09:00
Problem: https://yukicoder.me/problems/no/2546

問題概要

$N$ 個の等差数列がある。等差数列 $i$ は初項 $A_i$、交差 $D_i$ である。

各等差数列 $i$ から先頭 $X_{i}$ 個を選ぶ。ここで、$X_{1} + X_{2} + \dots + X_{N} = M$ となるようにする。

選んだ数の総和の最大値を求めよ。

制約

$N, M \le 3 \times 10^{5}$

解法メモ

めちゃくちゃ面白い！！

交差が $0$ 以上であるものについては、1 箇所だけから選ぶようにするのが良いことが言える（「交換しても悪化しない」の議論）
交差が負であるものについては、いわゆる資源配分問題（M 凹関数の和の最大化）になっており、priority_queue を用いた貪欲法が最適であることが言える

交差が $0$ 以上のところから合計 $0, 1, 2, \dots$ 個を選ぶ方法と、交差が負のところから合計 $0, 1, 2, \dots$ 個を選ぶ方法をそれぞれ求めてあげて、その結果をマージすればよい。交差が負のところは簡単。交差が $0$ 以上のところを考える。

交差が $0$ 以上のところについて

関数

$f_{i}(x) = \frac{x}{2}(D_{i} x + 2A_{i} - D_{i})$

を考えて、$x = 0, 1, 2, \dots, m$ について $\min_{i}f_{i}(x)$ を求める問題である。いわゆる行最小値問題である。 $x$ を固定したときに、

$\min_{i} (D_{i} x + 2A_{i} - D_{i})$

を求めることができればよいことがわかる。これは一次関数群なので Convex Hull Trick (Li Chao Tree) で求めることができる。

あるいは後述するように、$x > 0$ の領域に限定すると、関数群 $f_1, f_2, \dots$ は Pairwise Single Crossing であるので、General Li Chao Tree で解ける。

関数群 $f_1, f_2, \dots$ の性質

関数群 $f_1, f_2, \dots$ は Monge ではない
関数群 $f_1, f_2, \dots$ は定義域全体で見ると Pairwise Single Crossing でもない
しかし、$x > 0$ の領域に限定すると、関数群 $f_1, f_2, \dots$ は Pairwise Single Crossing である
- なので、一次関数群に帰着しなくても General Li Chao Tree で解ける

Depends on

Code

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

#include <bits/stdc++.h>
using namespace std;

#include "template.hpp"
#include "general_li_chao_tree.hpp"

/*
    f[a,d](m) = (A*2 + D(m-1)) * m / 2
*/
int main() {
    ll N, M, a, d, INF = 1LL << 60;
    cin >> N >> M;
    vll PA, PD;
    priority_queue<pll> que;
    REP(i, N) {
        cin >> a >> d;
        if (d >= 0) PA.EB(a), PD.EB(d);
        else que.push(pll(a, d));
    }

    vll plus(M+1, -INF), minus(M+1, -INF);
    auto make_func = [&](ll a, ll d) {
        return [&, a, d](ll m) -> ll {
            return (-d * (m - 1) - a * 2) * m / 2;
        };
    };
    GeneralLiChaoTree<ll, decltype(make_func(0, 0))> cht(0, M+1);
    REP(i, PA.size()) cht.insert(make_func(PA[i], PD[i]));
    plus[0] = minus[0] = 0;
    for (int m = 1; m <= M; m++) {
        if (PA.size()) plus[m] = -cht.query(m).first;
        if (!que.empty()) {
            auto [s, d] = que.top();
            que.pop();
            minus[m] = minus[m-1] + s;
            que.push(pll(s+d, d));
        }
    }

    ll res = -INF;
    REP(m, M+1) chmax(res, plus[m] + minus[M-m]);
    cout << res << endl;
}

#line 1 "tests/yukicoder/yukicoder_2546_cht_general_and_M_convex_priority_queue.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/2546"

#include <bits/stdc++.h>
using namespace std;

#line 4 "template.hpp"
using namespace std;

// My library is in https://github.com/drken1215/algorithm
#line 4 "Others/macro.hpp"
using namespace std;

using ll = long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pint = pair<int, int>;
using pll = pair<long long, long long>;
using tll = array<long long, 3>;
using fll = array<long long, 4>;
using vint = vector<int>;
using vll = vector<long long>;
using dint = deque<int>;
using dll = deque<long long>;
using vvint = vector<vector<int>>;
using vvll = vector<vector<long long>>;
using vpll = vector<pair<long long, long long>>;
template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); }
template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); }
template<class S, class T> inline auto maxll(S a, T b) { return max(ll(a), ll(b)); }
template<class S, class T> inline auto minll(S a, T b) { return min(ll(a), ll(b)); }
template<class T> auto max(const T &a) { return *max_element(a.begin(), a.end()); }
template<class T> auto min(const T &a) { return *min_element(a.begin(), a.end()); }
template<class T> auto argmax(const T &a) { return max_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto argmin(const T &a) { return min_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto accum(const vector<T> &a) { return accumulate(a.begin(), a.end(), T()); }
template<class T> auto accum(const deque<T> &a) { return accumulate(a.begin(), a.end(), T()); }

#define REP(i, a) for (long long i = 0; i < (long long)(a); i++)
#define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++)
#define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i)
#define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i)
#define EB emplace_back
#define PF push_front
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(x) x.begin(), x.end()
#line 3 "Others/stl_container_stream.hpp"
using namespace std;

// input stream
template<class T> istream& operator >> (istream &is, vector<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, deque<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, vector<vector<T>> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }

// output stream
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class S, class T> ostream& operator << (ostream &s, const pair<S, T> &P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 2> &P)
{ return s << '<' << P[0] << "," << P[1] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 3> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 4> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << "," << P[3] << '>'; }
template<class T> ostream& operator << (ostream &s, const vector<string> &P)
{ for (int i = 0; i < P.size(); ++i) { s << P[i] << endl; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const deque<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<vector<T>> &P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, const set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const multiset<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const unordered_set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const unordered_map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }

// Yes/No
void yes(bool a) { cout << (a ? "yes" : "no") << endl; }
void YES(bool a) { cout << (a ? "YES" : "NO") << endl; }
void Yes(bool a) { cout << (a ? "Yes" : "No") << endl; }
#line 4 "Optimization/general_li_chao_tree.hpp"
using namespace std;

// General Li-Chao Tree (Dynamic ver.) for Pairwise Single Crossing Functions
template<class VAL, class FUNC, class X = long long> struct DynamicGeneralLiChaoTree {
    struct Node {
        int id = -1;  // function id
        Node *left = nullptr, *right = nullptr;
    };
    
    // inner values using chunk-based memory pool
    vector<unique_ptr<Node[]>> blocks;
    vector<FUNC> funcs;
    Node *root = nullptr;
    X XL, XR;
    VAL INF = numeric_limits<VAL>::max() / 2;
    
    // constructors
    explicit DynamicGeneralLiChaoTree(X xl, X xr, VAL inf = numeric_limits<VAL>::max() / 2)
    : XL(xl), XR(xr), INF(inf) {
        assert(xl < xr);
    }

    // basic functions
    void reserve_functions(size_t n) {
        funcs.reserve(n);
    }
    VAL eval(int id, X x) const {
        return funcs[id](x);
    }
    bool better(int fid, int gid, X x) const {
        VAL a = eval(fid, x), b = eval(gid, x);
        return (a < b) || (a == b && fid < gid);
    }
    void clear() {
        funcs.clear();
        blocks.clear();
        used = BLOCK;
        root = nullptr;
    }

    // insert(f), in O(log X)
    int insert(FUNC f) {
        int id = (int)funcs.size();
        funcs.push_back(std::move(f));
        insert_at(root, XL, XR, id);
        return id;
    }

    // insert_segment(l, r, f), in O(log^2 X)
    int insert_segment(FUNC f, X l, X r) {
        assert(XL <= l && l <= r && r <= XR);
        int id = (int)funcs.size();
        funcs.push_back(std::move(f));
        if (l != r) insert_segment_at(root, XL, XR, l, r, id);
        return id;
    }

    // query(x), in O(log X)
    pair<VAL, int> query(X x) const {
        assert(XL <= x && x < XR);
        VAL best = INF;
        int best_id = -1;
        Node *p = root;
        X left = XL, right = XR;
        while (p) {
            if (p->id != -1) {
                int fid = p->id;
                VAL y = eval(fid, x);
                if (best_id == -1 || y < best || (y == best && fid < best_id)) {
                    best = y, best_id = fid;
                }
            }
            if (right - left == 1) break;
            X mid = (left + right) / 2;
            if (x < mid) p = p->left, right = mid;
            else p = p->right, left = mid;
        }
        return {best, best_id};
    }

private:
    // chunk-based node allocation
    static constexpr int BLOCK = 4096;
    int used = BLOCK;
    Node *new_node() {
        if (used == BLOCK) {
            blocks.emplace_back(make_unique<Node[]>(BLOCK));
            used = 0;
        }
        return &blocks.back()[used++];
    }

    // inner insert
    void insert_at(Node *&p, X left, X right, int fid) {
        Node **cur = &p;
        while (true) {
            if (!*cur) *cur = new_node();
            Node *v = *cur;
            int gid = v->id;
            if (gid == -1) {
                v->id = fid;
                return;
            }
            bool left_better = better(fid, gid, left), right_better = better(fid, gid, right - 1);
            if (!left_better && !right_better) return;
            if (left_better && right_better) {
                v->id = fid;
                return;
            }
            X mid = (left + right) / 2;
            bool mid_better = better(fid, gid, mid);
            if (mid_better) v->id = fid, fid = gid;
            if (left_better != mid_better) cur = &v->left, right = mid;
            else cur = &v->right, left = mid;
        }
    }

    // inner insert_segment
    void insert_segment_at(Node *&p, X left, X right, X l, X r, int fid) {
        if (r <= left || right <= l) return;
        if (l <= left && right <= r) {
            insert_at(p, left, right, fid);
            return;
        }
        if (!p) p = new_node();
        X mid = (left + right) / 2;
        if (l < mid) insert_segment_at(p->left, left, mid, l, r, fid);
        if (mid < r) insert_segment_at(p->right, mid, right, l, r, fid);
    }
};

// General Li-Chao Tree (Coordinate Compression ver.) for Pairwise Single Crossing Functions
template<class VAL, class FUNC, class X = long long> struct GeneralLiChaoTree {
    // inner values
    int N, XL, SIZ;
    bool compressed = true;
    VAL INF = numeric_limits<VAL>::max() / 2;
    vector<X> xs;
    vector<int> ids;
    vector<FUNC> funcs;

    // constructors
    explicit GeneralLiChaoTree(vector<X> xs_, VAL inf = numeric_limits<VAL>::max() / 2, bool sorted = true) 
    : N((int)xs_.size()), XL(0), SIZ(1), compressed(true), INF(inf), xs(std::move(xs_)) {
        if (!sorted) {
            sort(xs.begin(), xs.end());
            xs.erase(unique(xs.begin(), xs.end()), xs.end());
        }
        while (SIZ < N) SIZ <<= 1;
        ids.assign(SIZ << 1, -1);
    }
    explicit GeneralLiChaoTree(int xl, int xr, VAL inf = numeric_limits<VAL>::max() / 2) 
    : N(xr - xl), XL(xl), SIZ(1), compressed(false), INF(inf) {
        assert(N >= 0);
        while (SIZ < N) SIZ <<= 1;
        ids.assign(SIZ << 1, -1);
    }

    // basic functions
    void reserve_functions(size_t n) {
        funcs.reserve(n);
    }
    VAL eval(int id, X x) const {
        return funcs[id](x);
    }
    bool better(int fid, int gid, X x) const {
        VAL a = eval(fid, x), b = eval(gid, x);
        return (a < b) || (a == b && fid < gid);
    }
    void clear() {
        funcs.clear();
        fill(ids.begin(), ids.end(), -1);
    }

    // insert(f), in O(log N)
    int insert(FUNC f) {
        int id = (int)funcs.size();
        funcs.push_back(std::move(f));
        if (N) insert_at(1, 0, SIZ, id);
        return id;
    }

    // insert_segment(f, l, r), in O(log^2 N)
    int insert_segment(FUNC f, X l, X r) {
        assert(l <= r);
        int id = (int)funcs.size();
        funcs.push_back(std::move(f));
        if (N == 0 || l == r) return id;
        int L = lower_bound_index(l);
        int R = lower_bound_index(r);
        if (L == R) return id;
        int a = L + SIZ, b = R + SIZ;
        while (a < b) {
            if (a & 1) {
                int v = a++;
                int depth = 31 - __builtin_clz((unsigned)v);
                int length = SIZ >> depth;
                int left = (v - (1 << depth)) * length;
                insert_at(v, left, left + length, id);
            }
            if (b & 1) {
                int v = --b;
                int depth = 31 - __builtin_clz((unsigned)v);
                int length = SIZ >> depth;
                int left = (v - (1 << depth)) * length;
                insert_at(v, left, left + length, id);
            }
            a >>= 1, b >>= 1;
        }
        return id;
    }

    // query(x), x must be in xs, in O(log N)
    pair<VAL, int> query(X x) const {
        int pos = 0;
        if (compressed) {
            auto it = lower_bound(xs.begin(), xs.end(), x);
            assert(it != xs.end() && *it == x);
            pos = int(it - xs.begin());
        } else {
            assert(X(XL) <= x && x < X(XL + N));
            pos = int(x - XL);
        }
        VAL best = INF;
        int best_id = -1;
        int v = pos + SIZ;
        while (v) {
            int fid = ids[v];
            if (fid != -1) {
                VAL y = eval(fid, x);
                if (best_id == -1 || y < best || (y == best && fid < best_id)) {
                    best = y, best_id = fid;
                }
            }
            v >>= 1;
        }
        return {best, best_id};
    }

private:
    // coordinate compression
    int lower_bound_index(X x) const {
        if (compressed) {
            return int(std::lower_bound(xs.begin(), xs.end(), x) - xs.begin());
        } else {
            if (x <= X(XL)) return 0;
            else if (x >= X(XL) + X(N)) return N;
            else return int(x - X(XL));
        }
    }

    // inner insert
    void insert_at(int v, int left, int right, int fid) {
        auto coord = [&](int i) -> X { 
            i = min(i, N - 1);
            return (compressed ? xs[i] : X(i) + X(XL));
        };
        while (true) {
            int gid = ids[v];
            if (gid == -1) {
                ids[v] = fid;
                return;
            }
            bool left_better = better(fid, gid, coord(left));
            bool right_better = better(fid, gid, coord(right - 1));
            if (!left_better && !right_better) return;
            if (left_better && right_better) {
                ids[v] = fid;
                return;
            }
            X mid = (left + right) / 2;
            bool mid_better = better(fid, gid, coord(mid));
            if (mid_better) ids[v] = fid, fid = gid;
            if (left_better != mid_better) {
                v <<= 1;
                right = mid;
            } else {
                v = v << 1 | 1;
                left = mid;
            }
        }
    }
};
#line 8 "tests/yukicoder/yukicoder_2546_cht_general_and_M_convex_priority_queue.test.cpp"

/*
    f[a,d](m) = (A*2 + D(m-1)) * m / 2
*/
int main() {
    ll N, M, a, d, INF = 1LL << 60;
    cin >> N >> M;
    vll PA, PD;
    priority_queue<pll> que;
    REP(i, N) {
        cin >> a >> d;
        if (d >= 0) PA.EB(a), PD.EB(d);
        else que.push(pll(a, d));
    }

    vll plus(M+1, -INF), minus(M+1, -INF);
    auto make_func = [&](ll a, ll d) {
        return [&, a, d](ll m) -> ll {
            return (-d * (m - 1) - a * 2) * m / 2;
        };
    };
    GeneralLiChaoTree<ll, decltype(make_func(0, 0))> cht(0, M+1);
    REP(i, PA.size()) cht.insert(make_func(PA[i], PD[i]));
    plus[0] = minus[0] = 0;
    for (int m = 1; m <= M; m++) {
        if (PA.size()) plus[m] = -cht.query(m).first;
        if (!que.empty()) {
            auto [s, d] = que.top();
            que.pop();
            minus[m] = minus[m-1] + s;
            que.push(pll(s+d, d));
        }
    }

    ll res = -INF;
    REP(m, M+1) chmax(res, plus[m] + minus[M-m]);
    cout << res << endl;
}

yukicoder No.2546 Many Arithmetic Sequences (tests/yukicoder/yukicoder_2546_cht_general_and_M_convex_priority_queue.test.cpp)