Codeforces 1137E - Train Car Selection

题目传送门
感觉官方题解已经讲得很好了……
有很多log的做法，但其实是可以线性的。（额，谁教教我log怎么做啊QAQ）

首先，我们注意到，每次加进去的一组0都是一起增加的，所以我们只需要关心这组0中的第一个（因为后面的肯定会永远大于等于第一个）。

然后我们又注意到，如果在最前面加入一些0，那么除了第一个以外的都永远不会是最大的，那么就相当于让所有 $A_{i} = 0$ 。

所以我们只需要关心2和3两个操作。

我们把所有 $(x, A_{x})$ 转化到二维平面上，然后维护一条向左下凸的折线，显然不在这个折线上的就永远不会是答案了。实际上答案就是折线上最后的点，就是右下角那个。

于是2操作就是加个点，然后和求凸包差不多，会删掉末尾的一些点。

3操作的话，我们发现经过操作之后所有线段的斜率都会变大，所以经过操作后凸折线的最后若干个点可能会“翘起来”，所以我们只需要从后往前，把那些“翘起来”的点删掉就行了。

有个小技巧。我们可以记录一下 $b [i], s [i]$ 的前缀和，再结合点 $(x, A_{x})$ 是在第几个操作加进来的，就可以O(1)算出 $A_{x}$ ，而不用在每次进行3操作后给每个凸折线上的点都加一波。

我计算几何弱渣，所以写得很丑QAQ

#include<bits/stdc++.h>
#define ll long long
#define x1 _x1
#define y1 _y1
#define x2 _x2
#define y2 _y2
#define fr(i,x,y) for(int i=(x);i<=(y);i++)
#define rf(i,x,y) for(int i=(x);i>=(y);i--)
#define frl(i,x,y) for(int i=(x);i<(y);i++)
using namespace std;
const int N=300003;
int n,m;
ll b[N],s[N];
struct data{
	int num,x;
}st[N];  //这是一个栈，维护凸折线上的点
int L;

inline int sign(ll &x){
	if (x>0) return 1;
	if (x<0) return -1;
	return 0;
}

inline int mul(ll x1,ll y1,ll x2,ll y2){  //这个是判断叉积是否>0的
	int w1=sign(x1)*sign(y2),w2=sign(y1)*sign(x2);
	if (w1!=w2) return w1>w2;
	if (w1==0) return 0;
	return (long double)x1*y2>(long double)y1*x2;
}

void read(int &x){ scanf("%d",&x); }
void read(ll &x){ scanf("%lld",&x); }

void chkmin(ll &x,ll y){ if (y<x) x=y; }

inline ll cal(data q,int w){ //计算A[q.x]
	return b[w]-b[q.num]+1ll*(q.x-1)*(s[w]-s[q.num]);
}

void AddPoint(int w,int x){
	if (cal(st[L],w)==0) return;
	ll y=cal((data){w,x},w);
	while(L>=2){
		if (mul(st[L].x-st[L-1].x,cal(st[L],w)-cal(st[L-1],w),x-st[L].x,y-cal(st[L],w))) break;
		L--;
	}
	st[++L]=(data){w,x};
}

void PopBack(int w){
	while(L>=2&&cal(st[L],w)>=cal(st[L-1],w)) L--;
}

int main(){
	read(n);read(m);
	int tp;ll x,y;
	st[L=1]=(data){0,1};
	fr(i,1,m){
		b[i]=b[i-1];s[i]=s[i-1];
		read(tp);read(x);
		if (tp==1){
			b[i]=s[i]=0;
			st[L=1]=(data){i,1};
			n+=x;
		}else if (tp==2){
			AddPoint(i,n+1);
			n+=x;
		}else{
			read(y);
			b[i]+=x;s[i]+=y;
			PopBack(i);
		}
		printf("%d %lld\n",st[L].x,cal(st[L],i));
	}
	return 0;
}