# 贸易：题解

> 并列方案：离线离散化线段树。Codex（GPT-6）采用的解法，程序见 [alternative.cpp](alternative.cpp)；与出题人解法的比较见[主题解](solution.zh.md)。


## 按价格和编号排序

出售顺序是 $(c_i,i)$ 从大到小。价格会改变，但全部操作可以预先读入，因此先收集每种货物的初始二元组和所有改价后可能出现的二元组，排序去重，建立固定坐标。

某种货物在任一时刻只在它当前的价格坐标上有效。旧坐标的库存、产量均置零；改价时把库存和当前产量转移到新坐标。这个离散化过程不会提前执行操作，只是预先确定所有可能的位置。

## 线段树维护什么

每个区间保存四个量：精确库存总数 $S$ 、产量总数 $R$ 、库存总价值 $V$ 、每单位生产参数对应的价值 $W$ .后两项对模数 $P=10^9+7$ 取模。

生产 $t$ 时：

$$S\leftarrow S+Rt,\qquad V\leftarrow V+Wt\pmod P$$

整个区间的库存全部售空时，把 $S,V$ 清零，$R,W$ 不变，因为货物以后还可以继续生产。

维护“清空库存”和“累计生产时间”两个懒标记。清空时消除旧生产标记；之后的新生产继续累加。下传时必须**先清空，再生产**。修改单个坐标前下传沿途标记，使过去的生产使用过去的产量和价格归属。

## 如何出售

从最高价格一侧，也就是线段树右子树开始。

- 若当前区间库存不超过剩余需求 $k$ ，把整段价值计入收入，减少 $k$ ，并整体清空。
- 若到达叶子且库存更多，只出售 $k$ 件，以该叶子的价格计算收入。
- 否则先处理右子树，再在需求未满足时处理左子树。

一次出售只会有一个部分售出的边界位置，其余访问到的兄弟区间都能整体处理，所以花费 $O(\log U)$ ，其中 $U$ 为离散化后的坐标数。不能逐件出售，也不能按货物种类逐个扫描。

产量修改只改变当前叶子的 $R,W$ ，已有库存保持不变。价格修改先取出旧叶子的库存并清空该坐标，再在新坐标设置库存和产量，用新价格重新计算价值。同价时坐标按编号排序，天然满足编号大的先出售。

## 正确性

归纳每次操作前，所有有效叶子保存当前货物的精确库存和产量，区间总量与懒标记正确表示尚未下传的操作。生产公式逐件累加了应新增的库存；清空只移除现有库存；两类单点修改保留了题目要求不变的数量。出售按二元组的降序依次消耗库存，整段处理与逐件执行等价，因此输出的模收入正确。

## 数值范围与复杂度

库存必须精确保存，不能取模，否则无法与出售需求比较。用 $n$ 、操作数 $m$ 、最大产量 $p_{max}$ 和最大生产参数 $t_{max}$ 表示，整个过程累计生产量不超过 $nmp_{max}t_{max}$ .本题这个上界为 $9\times10^{18}$ ，仍在有符号 64 位范围内。计算价值时先对件数取模，避免把完整库存直接乘价格。

$U\le n+m$ .预处理、建树和所有操作合计 $O((n+m)\log(n+m+1))$ 时间，空间 $O(n+m)$ .读取全部操作是为了离散化，输出仍严格遵循原操作顺序。

独立模型用数组直接生产、改价和改产量，每次出售重新按价格与编号排序。对拍覆盖同价次序、零价格、零产量、生产后改价、售空后再生产、单种货物、超额出售和库存上界。正式数据还包含大量连续改价和最大累计库存。

## 程序与复现

本方案程序见 [alternative.cpp](alternative.cpp)。使用 C++17 编译后，可用 `tests/generate.py --out-dir <题目目录以外的路径> --std <程序路径>` 生成输入和答案。固定种子与用例目的见 [生成计划](tests/plan.json)。性能测量见 [评测环境与性能](../../../docs/评测环境与性能.md)。