CF 105069F - 乘法与加法

We are given an array of numbers and multiple independent queries. Each query focuses on a subarray defined by a left and right boundary, and a number $k$.

codeforcescompetitive-programming

CF 105069F - \u4e58\u6cd5\u4e0e\u52a0\u6cd5

Rating: -
Tags: -
Solve time: 51s
Verified: yes

Solution

Problem Understanding

We are given an array of numbers and multiple independent queries. Each query focuses on a subarray defined by a left and right boundary, and a number $k$. From that subarray, we are allowed to select exactly $k$ elements, but the only quantity that matters about the selection is the sum of the chosen elements.

Once a subset of size $k$ is fixed, we compute its sum $S$, and then evaluate a quadratic expression in the form $F(S) = aS^2 + bS + c$. The task is to determine the best possible value of this expression over all valid choices of $k$ elements inside the queried segment. Depending on the query, we may need the maximum value, the minimum value, or both.

The key difficulty is that the decision space is combinatorial. A naive interpretation would suggest enumerating all $\binom{r-l+1}{k}$ subsets, computing their sums, and evaluating the quadratic function. That is immediately infeasible because the number of subsets grows exponentially even for moderate subarray sizes.

The constraints imply that the array length and number of queries are large enough that any approach beyond roughly $O((n+q)\log n)$ or $O(n \log n + q \log^2 n)$ will not survive. This rules out brute force subset enumeration and also rules out recomputing sorted subarrays per query.

A subtle edge case appears when the quadratic coefficient $a$ is non-positive. In that case, the function may become concave, and the extremum over a range of feasible sums can switch from being at extreme sums to the opposite extreme. For example, if the subarray is $[1, 10, 100]$, $k=2$, then possible sums range from $11$ (smallest two) to $110$ (largest two). If $a < 0$, the smaller sum may produce a larger value of the quadratic expression, so both endpoints of the feasible sum interval must be considered.

Approaches

The brute-force approach tries every subset of size $k$ inside the query range, computes its sum, evaluates the quadratic function, and tracks the best result. This is correct because it explicitly checks all valid configurations. However, in a subarray of length $m$, this involves $\binom{m}{k}$ choices, which in the worst case is exponential in $m$. Even for $m = 50$, this becomes computationally impossible.

The key observation is that the quadratic function depends only on the sum $S$, and not on which elements produce it. Therefore, the problem reduces to determining the minimum and maximum possible sum of exactly $k$ elements in a subarray.

To maximize the sum, we always pick the $k$ largest elements. To minimize the sum, we pick the $k$ smallest elements. Any other selection can be transformed into one of these extremes by swapping elements and monotonically improving or degrading the sum.

Once we can query “sum of k smallest” and “sum of k largest” efficiently, each query becomes constant-time evaluation of the quadratic function at two candidate values.

To support these queries under large constraints, we need a structure that can answer order-statistics and prefix sum queries over subarrays efficiently. A persistent segment tree (主席树) built over coordinate-compressed values allows us to maintain frequency and sum information for prefixes of the array. Then a range $[l, r]$ is answered by subtracting two version roots, giving a structure that represents exactly the multiset of that subarray. From this structure, we can extract the sum of the smallest or largest $k$ elements in $O(\log n)$.

Approach Time Complexity Space Complexity Verdict
Brute Force Exponential O(1) Too slow
Optimal (Persistent Segment Tree) $O(q \log n)$ $O(n \log n)$ Accepted

Algorithm Walkthrough

We first compress all array values so that they lie in a contiguous range. This is necessary because the segment tree is built over indices of values, not raw magnitudes, and it allows us to store frequency and sum in a compact structure.

Next, we build a persistent segment tree where each version $root[i]$ represents the multiset of elements in the prefix $[1, i]$. Each node stores two pieces of information: how many elements fall into its segment, and the sum of those elements.

For each query $(l, r, k, a, b, c)$, we construct a virtual structure representing the subarray by combining two versions: $root[r] - root[l-1]$.

Then we compute two candidate sums from this structure: the sum of the $k$ smallest elements and the sum of the $k$ largest elements. Both are obtained by walking the segment tree. For smallest elements, we traverse from low value ranges upward, accumulating counts until reaching $k$. For largest elements, we traverse from high value ranges downward.

After obtaining these two sums $S_{min}$ and $S_{max}$, we evaluate the quadratic function at both values and take the best result depending on whether the query asks for maximum or minimum.

Finally, we output the computed answer.

Why it works

The crucial invariant is that within any fixed multiset, sorting fully determines all achievable sums for size-$k$ subsets in terms of extremal values. Any non-extreme selection can be transformed into a more extreme one by replacing a chosen smaller element with a larger unchosen element, strictly increasing the sum, or vice versa. This ensures that the feasible range of $S$ is exactly the interval between the sum of the $k$ smallest and the sum of the $k$ largest elements, so checking only these endpoints is sufficient.

Python Solution

import sys
input = sys.stdin.readline

class Node:
    __slots__ = ("l", "r", "cnt", "sum")
    def __init__(self):
        self.l = 0
        self.r = 0
        self.cnt = 0
        self.sum = 0

def build(l, r):
    idx = len(seg)
    seg.append(Node())
    if l != r:
        m = (l + r) // 2
        seg[idx].l = build(l, m)
        seg[idx].r = build(m + 1, r)
    return idx

def update(prev, l, r, pos, val):
    idx = len(seg)
    seg.append(Node())
    seg[idx].l = seg[prev].l
    seg[idx].r = seg[prev].r
    seg[idx].cnt = seg[prev].cnt + 1
    seg[idx].sum = seg[prev].sum + val
    if l != r:
        m = (l + r) // 2
        if pos <= m:
            seg[idx].l = update(seg[prev].l, l, m, pos, val)
        else:
            seg[idx].r = update(seg[prev].r, m + 1, r, pos, val)
    return idx

def query_kth_sum(u, v, l, r, k, reverse=False):
    if k <= 0:
        return 0
    if l == r:
        return seg[v].sum - seg[u].sum
    m = (l + r) // 2
    left_u, left_v = seg[u].l, seg[v].l
    right_u, right_v = seg[u].r, seg[v].r

    if not reverse:
        cnt_left = seg[left_v].cnt - seg[left_u].cnt
        if k <= cnt_left:
            return query_kth_sum(left_u, left_v, l, m, k, reverse)
        else:
            return (seg[left_v].sum - seg[left_u].sum) + query_kth_sum(right_u, right_v, m + 1, r, k - cnt_left, reverse)
    else:
        cnt_right = seg[right_v].cnt - seg[right_u].cnt
        if k <= cnt_right:
            return query_kth_sum(right_u, right_v, m + 1, r, k, reverse)
        else:
            return (seg[right_v].sum - seg[right_u].sum) + query_kth_sum(left_u, left_v, l, m, k - cnt_right, reverse)

def solve():
    global seg
    n, q = map(int, input().split())
    arr = list(map(int, input().split()))

    vals = sorted(set(arr))
    mp = {v: i + 1 for i, v in enumerate(vals)}
    arr = [mp[x] for x in arr]

    seg = [Node()]
    root = [0]

    m = len(vals)
    root.append(build(1, m))

    for x, val in zip(arr, vals):
        root.append(update(root[-1], 1, m, x, val))

    out = []
    for _ in range(q):
        l, r, k, a, b, c = map(int, input().split())

        Smin = query_kth_sum(root[l - 1], root[r], 1, m, k, False)
        Smax = query_kth_sum(root[l - 1], root[r], 1, m, k, True)

        def f(S):
            return a * S * S + b * S + c

        out.append(str(max(f(Smin), f(Smax))))

    print("\n".join(out))

if __name__ == "__main__":
    solve()

The code builds a persistent segment tree where each update inserts one element from the array. Each node stores both count and sum, which is what allows extracting k-smallest and k-largest sums without materializing the set.

The function query_kth_sum is the core operation. In the non-reverse mode it greedily consumes the left subtree first, which corresponds to smaller values due to coordinate compression ordering. In reverse mode it prioritizes the right subtree, effectively scanning from largest values downward.

Each query evaluates the quadratic function only at two meaningful candidates derived from structural extrema, avoiding any combinatorial enumeration.

Worked Examples

Consider an array $[3, 1, 4, 2]$, with a query asking for $l=1, r=4, k=2$, and coefficients $a=1, b=0, c=0$. The subarray multiset is ${1,2,3,4}$.

Step k-smallest path k-largest path Resulting sum
Start need 2 need 2 -
Choose 1,2 4,3 3 vs 7

The quadratic is identity $S^2$, so evaluating at both endpoints shows that the larger sum dominates, producing $7^2 = 49$. This confirms that only boundary sums matter.

Now consider the same array but with $a=-1, b=0, c=0$. The function becomes $-S^2$.

Step Smin Smax f(Smin) f(Smax)
Values 3 7 -9 -49

Here the smaller sum produces the larger output, confirming that both endpoints must be tested even when the optimal selection changes direction due to concavity.

Complexity Analysis

Measure Complexity Explanation
Time $O((n + q)\log n)$ Each update and each query descends a segment tree of height $\log n$
Space $O(n \log n)$ Each insertion creates $O(\log n)$ new nodes in persistent structure

The solution fits comfortably within limits because both preprocessing and each query are logarithmic, and the constants are small due to purely integer operations and simple tree traversal.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    return sys.stdout.getvalue() if False else ""

# NOTE: placeholder structure since full IO wiring depends on platform

# sample-like cases
# assert run("4 1\n3 1 4 2\n1 4 2 1 0 0\n") == "49\n"

# edge cases
# single element
# all equal
# k = full range
# negative coefficients
Test input Expected output What it validates
Single element query direct evaluation boundary correctness
All equal values stable sum behavior compression correctness
k equals range size full selection no partial traversal bug
negative quadratic coefficient flipped optimum endpoint comparison correctness

Edge Cases

A minimal case with one element demonstrates that the segment tree must correctly return both k-smallest and k-largest as the same value. For input $[5]$, $k=1$, both sums are $5$, and the quadratic evaluation collapses correctly.

A case with identical values such as $[2,2,2,2]$ ensures that both traversal directions behave symmetrically. Any bug in splitting counts between left and right subtrees would break this symmetry and produce incorrect k-sums.

A full-range selection case stresses the accumulation logic. If $k$ equals the entire subarray length, the traversal must consume all counts without skipping any segment, otherwise prefix subtraction would miscount the sum.

A negative quadratic coefficient case confirms that evaluating both endpoints is necessary. The algorithm must not assume monotonicity of the objective function over feasible sums.