[CF1137E]Train Car Selection[维护凸壳]

题意

题目链接

分析

• 首先，如果加到了车头所有之前的车厢都不可能成为答案。

• 如果加到了车尾，容易发现对于 \(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;

}