Vasya 喜欢乘坐火车旅行，但不喜欢坐在车厢尾部。
Vaysa 到了火车站。列车共由 $n$ 节车厢组成，从头至尾编号为 $1, 2, \cdots, n$。接下来将会有三种不同的事件发生：
在列车的头部添加了若干节车厢。
在列车的尾部添加了若干节车厢。
Vasya 想重新计算一下列车中所有车厢的 "便利值" (具体见下文)。
每一时刻，我们都从 (当时的) 列车头数起，将各节车厢从 $1$ 到 $n$ 编号，我们用 $A_i$ 表示一节车厢的 "便利值" (ps: 对于一节固定的车厢，它的编号可能会改变，但是在重新计算之前它的 "便利值" 是不变的)。
"便利值" 的计算方式如下：
初始时刻的车厢和新加入的车厢的 "便利值" 为 $0$。
对于一次重新计算，Vasya 会指定两个正整数参数 $b, s$，然后令此时车厢 $i$ 的 "便利值" $A'_i \gets A_i + b + \left( i - 1 \right) \cdot s$。
由于 Vasya 还不知道他该什么时候离开火车，因此对于每个事件，他都想知道：当前哪节车厢的 便利值" 最小 (注意是最小，不是最大)。如果有多节车厢，则输出编号最小的 (由于 Vasya 不喜欢尾部)。
由于车厢数可能过多，他希望你写一个程序解决他的问题。
第一行包含两个正整数 $n, m$ ($n \leq 10^9; m \leq 3 \times 10^5$)，表示出发时列车中车厢的个数，以及事件的个数。
接下来的 $m$ 行，每行描述一个时间，格式如下：
1 k ($1 \leq k \leq 10^9$)，表示在列车头部添加 $k$ 节车厢。
2 k ($1 \leq k \leq 10^9$)，表示在列车尾部添加 $k$ 节车厢。
3 b s ($1 \leq b, s \leq 10^9$)，表示 Vasya 要重新计算列车中所有车厢的 "便利值"。
保证在任意时刻，列车的长度 (车厢的个数) 不超过 $10^9$，所有车厢的 "便利值" 不超过 $10^{18}$。
输出共 $m$ 行。对于每次事件结束，输出一行，包含两个整数 $j$ 和 $A_j$，表示 "便利值" 最小的车厢 (如果有相同则输出编号最小) 以及对应的 "便利值"。
首先，能够注意到一个很明显的性质：$s > 0$。也就是说，全局加的等差数列的公差为正。
因此，对于两节车厢 $i < j$，如果 $A_i \leq A_j$，则无论怎么 "重新计算"，$j$ 的舒适度永远不会小于 $i$，从而 $j$ 不会作为答案，把 $j$ 删掉。
又因为操作 1 相当于在序列头部加入 $0$。因此，有一个看似平凡但重要的结论：
一旦经过一次操作 1，编号 $> 1$ 的所有车厢都不再对答案产生贡献，可以看成这剩下唯一一节车厢 $A_1 = 0$ (也就是说问题重新开始)。
因此接下来只考虑存在操作 2 和操作 3 的情况。容易注意到，由于此时只可能在尾部加入，因此车厢的编号可以看成不变的。
考虑只有操作 3 的情况。设等差数列为 $k x + b$ (一次函数形式)。于是，$b$ 显然是没有用的，放到全局变量中最后加回来即可。
于是我们只需考虑 $k$。(我们不显式地加过去) 这相当于给定一个序列和正整数 $K$，求出 $a_i + i \cdot K$ 的最小值。
如果我们把 $\left( i, a_i \right)$ 看成点，则所求的点一定在这些点构成的凸包上，且它是斜率为 $- K$ 的下切线与凸包的交点 (参考斜率优化 DP)。
又因为这里的 $K = \sum k$ 是单调递增的，因此斜率也是单调的，故我们可以用单调栈来维护整个点集的下凸包。
最后找到那个切点就是答案，注意在弹栈过程中判断等号，由于要编号尽可能小，因此相等时也删去。
接下来考虑有操作 2 的情况。由于我们不显式地去加那个等差数列，而是通过记录全局 $K, B$ (即 offset, 偏移量) 来处理。因此对于新加入的 $0$，设编号为 $t$，我们应该加入点 $\left( t, - \left( K t + B \right) \right)$。
然后和斜率优化 DP 类似，我们要对于新加入的点，使用弹栈的方法维护出整个下凸包即可。
最后的时间复杂度就是萌萌哒 $O \left( n + m \right)$ 啦。
#include <bits/stdc++.h>
#define x second
#define y first
typedef long long ll;
typedef long double ld;
typedef std::pair <ll, ll> pr;
const int N = 300054;
int n, q;
ll K, B, tot;
pr a[N];
inline void reset() {K = B = 0, n = 1, *a = pr(0, 0);}
inline bool fy(const pr &u, const pr &v, ll K) {return u.y - v.y <= (ld)K * (v.x - u.x);}
inline bool fy(const pr &u, const pr &v, const pr &w) {return (ld)(u.y - v.y) * (w.x - v.x) <= (ld)(v.y - w.y) * (v.x - u.x);}
inline void push(const pr &t) {for (; n > 1 && fy(a[n - 2], a[n - 1], t); --n); a[n++] = t;}
inline void adjust(ll K) {for (; n > 1 && fy(a[n - 2], a[n - 1], K); --n);}
int main() {
int op, k, d; reset();
for (scanf("%lld%d", &tot, &q); q; adjust(K), printf("%lld %lld\n", a[n - 1].x + 1, a[n - 1].x * K + B + a[n - 1].y), --q)
switch (scanf("%d%d", &op, &k), op) {
case 1: reset(), tot += k; break;
case 2: push(pr(-K * tot - B, tot)), tot += k; break;
case 3: scanf("%d", &d), B += k, K += d; break;
}
return 0;
}
坑1：在判断斜率大小的过程中，如果使用移项两边乘法，则会爆 long long，需要使用 __int128 (然鹅 CF 不滋磁) 或 long double (此时你直接除下去也行)。
坑2：由于题目要求对相同情况输出编号最小的车厢，因此如果斜率相等 (或三点共线) 时也要 pop。