← 返回题目列表

Codeforces · 1137/E

E. 火车车厢选择

中文机器翻译题面 查看原题

Vasya 喜欢乘火车旅行,但不喜欢他乘坐的车厢位于火车尾部。

Vasya 在车站上车。火车由 $$$n$$$ 车厢组成,从机车(火车头)开始计数,索引从 $$$1$$$ 到 $$$n$$$。火车行驶时会发生三种类型的事件:

1. 车头增加一定数量的车厢;
2、列车尾部增加一定数量的车厢;
3. Vasya 重新计算汽车的便利性值(请阅读下面的更多信息)。

在每个时刻,我们都会从火车头索引车厢,从 $$$1$$$ 开始。请注意,当在火车头添加新车厢时,旧车厢的索引可能会发生变化。

为了选择进入哪辆车,Vasya 将为每辆车使用 $$$A_i$$$ 值(其中 $$$i$$$ 是汽车索引),计算如下:

- 行程开始时$$$A_i=0$$$,以及添加新车时。
- 在下一次重新计算期间,Vasya 选择一些正整数 $$$b$$$ 和 $$$s$$$ 并将其添加到所有 $$$A_i$$$ 值 $$$b + (i - 1) \cdot s$$$ 中。

Vasya 尚未决定他将在哪里上车和在哪里下车,因此在三种类型之一的每次事件之后,他想知道汽车的最小索引,使其值 $$$A_i$$$ 最小。由于汽车很多,Vasya 让你编写一个程序来回答他的问题。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 10^9$$$, $$$1 \leq m \leq 300\,000$$$),分别表示发车时列车的车厢数和车站数。

接下来的 $$$m$$$ 行包含事件的描述。每个事件都是以下三种类型之一:

- "$$$1$$$ $$$k$$$" ($$$1 \le k \le 10^9$$$),将 $$$k$$$ 车厢添加到火车头
- "$$$2$$$ $$$k$$$" ($$$1 \le k \le 10^9$$$),将 $$$k$$$ 车厢添加到火车尾部
- "$$$3$$$ $$$b$$$ $$$s$$$" ($$$1 \le b, s \le 10^9$$$),重新计算所有火车车厢的便利性。

保证任何时候列车长度不超过$$$10^9$$$。还保证整数 $$$A_i$$$ 不会增长得太高。形式上,可以保证,如果我们将 $$$3$$$-rd 类型的所有事件的最大加法相加(即 $$$b + (n - 1) \cdot s$$$,其中 $$$n$$$ 是当时的汽车数量),那么获得的总和最多为 $$$10^{18}$$$。

输出

在每个 $$$m$$$ 查询之后打印两个整数:$$$j$$$ 和 $$$A_j$$$ - 最靠近火车头的车厢编号,使其值 $$$A_j$$$ 最小,以及值 $$$A_j$$$ 本身。

示例

输入 #1

1 8
1 1
3 1 1
3 1 1
2 1
2 1
3 1 1
2 1
3 1 5

输出 #1

1 0
1 1
1 2
3 0
3 0
1 3
5 0
1 4

注意

- 最初火车由一节车厢组成,$$$A_1 = 0$$$,为简单起见,我们将火车表示为 $$$[0]$$$。
- 在头部添加一辆车后,火车是$$$[0, 0]$$$。
- 重新计算参数 $$$b=1, s=1$$$ 的值后,列车为 $$$[1, 2]$$$。
- 使用参数 $$$b=1, s=1$$$ 再次重新计算值后,列车为 $$$[2, 4]$$$。
- 在末尾添加一辆车后,火车为 $$$[2, 4, 0]$$$。
- 在最后添加一辆车后,火车是$$$[2, 4, 0, 0]$$$。
- 使用参数 $$$b=1$$$、$$$s=1$$$ 重新计算值后,列车为 $$$[3, 6, 3, 4]$$$。
- 在末尾添加一辆车后,火车为 $$$[3, 6, 3, 4, 0]$$$。
- 使用参数 $$$b=1$$$、$$$s=5$$$ 重新计算值后,列车为 $$$[4, 12, 14, 20, 21]$$$。