Hard version of this task: QOJ9609 幽默还是夢 (with arbitrary interval queries and modifications).

It seems that DP is not needed.

First, apply a difference transformation. The problem is equivalent to: given \(n\) types of items, each item has two possible purchase options: if you buy a size-1 version, you obtain a value of \(x_i\); and if you buy a size-2 version, you obtain a value of \(y_i\). For a prefix \([1,d]\) of the items, determine the maximum value obtainable when the total size of purchased items is exactly \(b\).

Consider how to solve the subtask first. Partition items into two categories:

• Category 1: \(x_i \ge y_i - x_i\). In this case, split the item directly into two independent size-1 items with values \(x_i\) and \(y_i - x_i\), and then simply apply a greedy algorithm.
• Category 2: \(x_i < y_i - x_i\), which is more tricky.

Key observation: If there exist two Category-2 items such that both are purchased in their size-1 forms, then this is never optimal — the solution can always be adjusted to obtain a better one (related problem: [PA 2026] Stosy naleśników). In other words, almost all Category-2 items are selected in their size-2 forms. This suggests treating each such item directly as an item of size 2 with value \(y_i\). Then sort items according to their value-to-size ratio (value divided by size) and apply a greedy strategy, followed by some adjustment (somewhat similar to [China NOIP 2025] 清仓甩卖).

Now discuss the details of the adjustment step:

• Sort items by value-to-size ratio. If the greedy process already reaches total size exactly \(b\), no adjustment is needed.
• Otherwise, the only possible case is that the last item purchased has size 2, making the total size \(b+1\). First, remove this last item; now the total size becomes \(b-1\). There are two options:
  • Remove a Category-1 item with the smallest value from the previously selected items and then add back the removed Category-2 item (in its size-2 form).
  • Either select a Category-1 item with the largest value from the remaining items, or pick a Category-2 item \(i\) with the largest \(x_i\) and purchase its size-1 version to gain value \(x_i\).

Direct simulation yields the subtask solution for \(d = N\). Next, we extend this to handle prefix queries: sort all queries by \(d\) in increasing order and perform a sweep line, maintaining the currently available items with a segment tree. Specifically, each index in the segtree corresponds to the item’s rank after sorting by value-to-size ratio. When advancing from \(d-1\) to \(d\), we insert the item whose original index is \(d\). For queries, first do a segtree binary search to find the split point — the rightmost position where the sum of sizes of available items on the left is \(\le b\). If the sum equals \(b-1\), simulate the adjustment operations: for this purpose, two additional segtrees are needed to maintain the prefix minimum / suffix maximum required by the adjustment step, and they should be updated synchronously during the sweep line.

The time complexity is \(O((N+Q)\log N)\), which easily fits within the time limit.