题意
分析
首先，如果加到了车头所有之前的车厢都不可能成为答案。
如果加到了车尾，容易发现对于 \(x_2<x_3\) 而言在某个时刻会出现 2 又比 3 优的情况。
-
具体来讲，如果存在 \(sx_3+b+y_3\ge sx_2+b+y_2\) ，那么 2 比 3 优。
推一推：\(-s<\frac{y_3-y_2}{x_3-x_2}\) ，所以维护一个下凸壳即可。
时间复杂度 \(O(n)\) 。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define pb push_back
#define re(x) memset(x, 0, sizeof x)
inline int gi() {
int x = 0,f = 1;
char ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
return x * f;
}
template <typename T> inline bool Max(T &a, T b){return a < b ? a = b, 1 : 0;}
template <typename T> inline bool Min(T &a, T b){return a > b ? a = b, 1 : 0;}
const int N = 3e5 + 7;
int n, m;
int tl;
LL k, b, val[N], tot;
typedef pair<LL, LL> pii;
#define mp make_pair
#define fi first
#define se second
pii q[N];
double getk(pii a, pii b) { return 1.0 * (b.se - a.se) / (b.fi - a.fi);}
LL calc(pii a) {
return a.fi * k + a.se + b;
}
int main() {
n = gi(), m = gi();
q[tl = 1] = mp(0, 0);
while(m--) {
int opt = gi();
if(opt == 1) {
q[tl = 1] = mp(0, 0);
n += gi();
k = b = 0;
}
if(opt == 2) {
pii now = mp(n, -(k * n + b));
while(tl > 1 && getk(q[tl], now) <= getk(q[tl - 1], q[tl])) --tl;
n += gi();
q[++tl] = now;
}
if(opt == 3) b += gi(), k += gi();
while(tl > 1 && calc(q[tl]) >= calc(q[tl - 1])) --tl;
printf("%lld %lld\n", q[tl].first + 1, calc(q[tl]));
}
return 0;
}