Overview

This problem asks us to find the maximum total score when connecting each song to its “immediately preceding song” using dynamic programming. Since the recurrence relation takes the form of a “maximum value of lines query”, we can speed up the computation using a Li Chao Tree (Convex Hull Trick).

Analysis

DP Formulation

Let \(dp_i\) be the maximum total score of a playlist where the last selected song is \(i\).

• If we choose song \(i\) as the first song: \(dp_i = A_i\)
• If we place song \(j\) (\(j < i\)) immediately before song \(i\): $\(dp_i = dp_j + A_i + B_j \times B_i\)$

Combining these two cases, we get the following recurrence relation:

\[dp_i = A_i + \max\Bigl(0,\ \max_{j<i}\bigl(dp_j + B_j \times B_i\bigr)\Bigr)\]

Here, the \(0\) in \(\max(0, \cdots)\) corresponds to the case where we start the playlist from song \(i\) without connecting anything before it.

The final answer is \(\max_i dp_i\).

Problem with the Naive Approach

If we check all \(j < i\) for each \(dp_i\), the time complexity will be \(O(N^2)\), which will result in a Time Limit Exceeded (TLE) for \(N \le 10^5\).

Optimization Idea

Let us focus on the core part of the recurrence relation:

\[\max_{j<i}\bigl(dp_j + B_j \times B_i\bigr)\]

If we let \(x = B_i\), this can be rewritten as:

\[\max_{j<i}\bigl(\underbrace{B_j}_{\text{slope}} \cdot x + \underbrace{dp_j}_{\text{intercept}}\bigr)\]

This represents the operation of finding the maximum value at \(x = B_i\) among multiple lines.

Thus, the flow is as follows: every time we finish processing song \(j\), we add a line with “slope \(B_j\) and intercept \(dp_j\)”. Then, when processing song \(i\), we query the maximum value at \(x = B_i\).

Algorithm

We can use a Li Chao Tree as the data structure to efficiently perform “adding a line” and “querying the maximum value at a given \(x\)” operations on a set of lines.

While the standard Convex Hull Trick requires the slopes or query points to be monotonic, in this problem, both \(B_j\) (slope) and \(B_i\) (query point) can be arbitrary integers. Therefore, the Li Chao Tree, which has no such constraints, is suitable.

The specific steps are as follows:

1. Since the candidates for the query points \(x = B_i\) are the values of \(B\) themselves, we coordinate compress the values of \(B\) and use them as the interval for the Li Chao Tree.
2. For \(i = 1, 2, \ldots, N\) in order:
   • Query the maximum value \(bp\) among the lines at \(x = B_i\).
   • If \(bp < 0\), replace it with \(0\) (the option of starting a new playlist from song \(i\)).
   • Calculate \(dp_i = A_i + bp\) and update the answer.
   • Insert the line with slope \(B_i\) and intercept \(dp_i\) into the Li Chao Tree.

By processing \(i\) in ascending order, we naturally guarantee the correct order where “only the lines for \(j < i\) have been added at the time of the query.”

How the Li Chao Tree Works

Each node in the tree stores a single line that is (potentially) the maximum in its interval.

• insert: Compare the new line with the node’s line at the midpoint of the interval. Keep the winning line at the node, and recursively pass the losing line down to the child node where it could still potentially be the maximum.
• query: Traverse down from the root to the leaf containing the query point, evaluating the value of the line at each visited node, and return the maximum of these values.

Both operations are completed in time proportional to the height of the tree, which is \(O(\log N)\).

Complexity

• Time Complexity: \(O(N \log N)\) (We perform an insert and a query in \(O(\log N)\) time for each song)
• Space Complexity: \(O(N)\) (For the node array of the Li Chao Tree)

Implementation Details

• 64-bit Integers: Since \(A_i\) and \(B_i\) can be up to around \(10^6\), terms like \(B_j \times B_i\) and their accumulation can become very large. NEG = -(1 << 62) is used as a sentinel to represent “no line exists yet” (Python handles arbitrarily large integers, so overflow is not an issue, but the design is mindful of the value range).

• Coordinate Compression: We compress the candidate query points using xs = sorted(set(B)) and map each value to its index using comp. The Li Chao Tree operates on this set of discrete points.

• Handling bp < 0: To handle the case where starting a new playlist from song \(i\) without connecting anything is better, we replace the maximum value with \(0\) if it is negative. This allows us to handle both the “single song score” and “connected score” in a unified manner.

• Order of Processing: By maintaining the order of “query \(\to\) DP computation \(\to\) insert” inside the loop for i in range(n), we ensure the correctness that only lines from songs before \(i\) are referenced.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    A = [0] * n
    B = [0] * n
    idx = 1
    for i in range(n):
        A[i] = int(data[idx]); B[i] = int(data[idx + 1])
        idx += 2

    xs = sorted(set(B))
    nn = len(xs)
    comp = {v: i for i, v in enumerate(xs)}
    NEG = -(1 << 62)
    size = 4 * nn
    M = [0] * size
    Bb = [NEG] * size

    def insert(nm, nb):
        node = 1; l = 0; r = nn - 1
        while True:
            mid = (l + r) >> 1
            xm = xs[mid]
            cm = M[node]; cb = Bb[node]
            if nm * xm + nb > cm * xm + cb:
                M[node] = nm; Bb[node] = nb
                nm, nb = cm, cb
            if l == r:
                return
            xl = xs[l]
            if nm * xl + nb > M[node] * xl + Bb[node]:
                node = node << 1; r = mid
            else:
                xr = xs[r]
                if nm * xr + nb > M[node] * xr + Bb[node]:
                    node = (node << 1) | 1; l = mid + 1
                else:
                    return

    def query(xi):
        x = xs[xi]
        node = 1; l = 0; r = nn - 1
        res = NEG
        while True:
            v = M[node] * x + Bb[node]
            if v > res:
                res = v
            if l == r:
                break
            mid = (l + r) >> 1
            if xi <= mid:
                node = node << 1; r = mid
            else:
                node = (node << 1) | 1; l = mid + 1
        return res

    ans = NEG
    for i in range(n):
        bi = B[i]
        xi = comp[bi]
        bp = query(xi)
        if bp < 0:
            bp = 0
        dpi = A[i] + bp
        if dpi > ans:
            ans = dpi
        insert(bi, dpi)

    print(ans)

main()

---

This editorial was generated by claude4.8opus-high.