CF1137E Train Car Selection（单调栈维护凸函数）
首先本题的关键是一次性加0操作只有第一个0是有用的。然后对于1 k操作，其实就是把之前的所有数删除。对于其他的情况，维护一次函数的和，将(i,a[i])看成平面上的一个点，用单调栈维护一下。
#include<bits/stdc++.h> using namespace std; const int N=3e5+7; #define int long long typedef pair<int,int>pii; int n,k,b,Q,top; pii st[N]; long double getk(pii a,pii b){return 1.0*(b.second-a.second)/(a.first-b.first);} int calc(pii a){return(a.first-1)*k+a.second+b;} signed main() { scanf("%lld%lld",&n,&Q); st[top=1]=pii(1,0); while(Q--) { int op,x,y;scanf("%lld%lld",&op,&x); if(op==1)st[top=1]=pii(1,0),k=b=0,n+=x; else if(op==2) { pii u=pii(n+1,-calc(pii(n+1,0))); while(top>1&&getk(u,st[top])>=getk(st[top],st[top-1]))--top; st[++top]=u,n+=x; } else scanf("%lld",&y),b+=x,k+=y; while(top>1&&calc(st[top])>=calc(st[top-1]))--top; printf("%lld %lld ",st[top].first,calc(st[top])); } }