GitHub 源文件 Markdown English

贸易¶

参考时间限制：2.0 秒（评测环境与性能）。
实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
内存限制：256 MB

背景故事¶

火星殖民地终于度过了物资紧缺的阶段，开始定期生产和出售货物。仓库按当前售价优先出售最贵的物品，生产能力和售价也会调整。请根据操作记录，计算每次出售得到的收入。

形式化问题描述¶

有 \(n\) 种货物，编号为 \(1\) 到 \(n\) .第 \(i\) 种货物的初始单价为 \(c_i\) ，初始产量参数为 \(p_i\) ，初始库存均为零。按顺序处理以下操作：

1 t ：生产。每种货物 \(i\) 的库存增加 \(p_it\) .
2 k ：出售。按单价从高到低出售至多 \(k\) 件物品；单价相同时，优先出售种类编号较大的物品。库存不足时卖出全部库存。输出这次收入对 \(10^9+7\) 取模的结果。
3 i p ：将种类 \(i\) 的产量参数改为 \(p\) ，不改变已有库存。
4 i c ：将种类 \(i\) 的单价改为 \(c\) ，已有库存也立即使用新价格。

未售出的物品一直保留。一次出售可以卖出同一种货物的任意件数；\(k\) 表示物品件数。

输入格式¶

第一行两个整数 \(n,m\) .第二行依次给出 \(n\) 对整数 \(c_i,p_i\) .接下来 \(m\) 行，每行按上述格式给出一个操作。

输出格式¶

对每个出售操作输出一行一个整数，表示本次收入对 \(10^9+7\) 取模的结果。没有出售操作时不输出任何整数。

样例 1¶

输入¶

输出¶

5
5
63

样例 2¶

输入¶

输出¶

5
5
0

样例 3¶

输入¶

1 5
0 0
1 1000
2 0
3 1 100000
1 1000
2 1000000000000000000

输出¶

0
0

样例解释¶

样例 1 第一次出售一件单价 \(3\) 的物品和两件单价 \(1\) 的物品，收入为 \(5\) .随后两次收入分别为 \(5\) 和 \(63\) .样例 2 首次同价出售优先消耗种类 \(2\) ，所以随后把种类 \(2\) 涨价不会改变剩余那件物品的售价。样例 3 中所有被出售物品的价格都是零。

数据范围与保证¶

所有数据满足 \(1\le n,m\le300000\) .所有初始及修改后的单价满足 \(0\le c_i,c\le10^9\) ，产量参数满足 \(0\le p_i,p\le100000\) .操作中 \(0\le t\le1000\) ，\(0\le k\le10^{18}\) ，\(1\le i\le n\) .

分值比例	额外条件
100%	无额外条件