贸易 题解¶
解法与取舍¶
出题人解法：在线伸展树。 在线伸展树作为标程：无需预知后续价格，空间为 \(O(n)\) ，每次操作摊还为 \(O(\log(n+1))\) .离线线段树需要预读操作及 \(O(n+m)\) 空间，但每次操作有最坏 \(O(\log(n+m+1))\) 的保证，适合允许预读且重视单次响应上界的场景。两者作为并列方案。
程序与署名： std.cpp 实现出题人解法；Codex（GPT-6）负责实现整理、边界处理与证明说明。Codex（GPT-6）采用的离线离散化线段树见 alternative.cpp 和并列方案题解。
按价格和编号维护有序树¶
每种货物对应一个 Splay 节点，以 \((c_i,i)\) 为键，按升序排列。出售从右侧开始，自然满足高价优先、同价时编号大者优先。节点按货物编号直接定位，价格改变时才删除再插入。
子树维护库存总数 \(S\) 、产量总数 \(R\) 、库存价值 \(V\) 、单位生产参数增加的价值 \(W\) .后两项对 \(P=10^9+7\) 取模，库存和产量保持精确整数。节点自身也保存这些信息，子树汇总由自身与左右孩子相加得到。
生产和清空标记¶
生产 \(t\) 时，
出售整棵子树的全部库存时，把 \(S,V\) 清零，保留 \(R,W\) .清空会覆盖此前尚未下传的生产，之后生产则累加到新的时间标记。下传顺序必须先清空、再生产。Splay 旋转前先从辅助树根到目标节点下传，使节点移动后不改变标记所属的货物集合；旋转后重新汇总。
出售与两类修改¶
出售只沿一条边界路径下降。先看右子树：若其库存超过需求，进入右子树；否则把该子树价值全部计入收入并清空。接着出售当前货物，仍有需求才进入左子树。只有一个部分售出的边界，其他经过的高价区域整段处理，不能逐件循环。结束时伸展最后访问的节点，并修复沿途汇总。
修改产量时先将对应节点伸展到根、下传标记，再改自身产量并重算汇总；库存不变。改价格时同样先伸展和下传，取下该节点并合并左右子树，然后用新键重新插入，已有库存与产量随货物一起移动。所有操作按输入顺序读取，不预读未来价格。
正确性与复杂度¶
有序树不变量保证出售次序正确。库存和生产标记公式与逐货物执行一致，清空不会改变以后生产能力，单点修改前的下传保证旧生产使用旧产量。整段出售等价于依次出售其中所有货物，因此收入正确。
每次查询边界后伸展，改单点、删除、插入和拼接只需常数次标准 Splay 访问，故每次操作摊还 \(O(\log(n+1))\) ；单次最坏可以为 \(O(n)\) .排序初始化和所有操作合计 \(O((n+m)\log(n+1))\) ，空间 \(O(n)\) .
总生产量不超过 \(nmp_{max}t_{max}\le9\times10^{18}\) ，可用有符号 64 位整数。价值乘法先对件数取模，避免完整库存乘价格溢出。树遍历与伸展下传使用显式栈；初始平衡建树只有对数递归深度。
验证与性能¶
各方案的五次重复计时与峰值内存记录见评测环境与性能。