CF1137E Train Car Selection

经典的凸包维护线段。

注意到操作是全体加上 一条斜率大于等于 $1$ 的线段，查询最小值及其位置，我们容易想到在凸包上考虑。具体地，从左到右有用的点的不仅 值 满足单调递减，与前一个形成的线段的斜率 也需要单调递减。直接维护下凸包。而对于全局加线段操作维护 全局标记 $sum_k,sum_b$。时间复杂度 $\mathcal O(m)$。

Code

#include<iostream>
#include<cstdio>
using namespace std;
using ll=long long ;
const int N=3e5+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
struct Point{ll x,y;}sta[N];
int n,m,top;
ll sumk,sumb;
inline ll f(const Point &now){return sumk*now.x+now.y+sumb;}
int main()
{
    read(n,m);
    sta[top=1]={0,0};
    while(m--)
    {
        int op,k;
        read(op);
        if(op==1)read(k),sta[top=1]={0,0},n+=k,sumk=sumb=0;
        else if(op==2)
        {
            read(k);
            Point now={n,-sumk*n-sumb};
            if(f(sta[top]))
                while(top>1&&(f(now)-f(sta[top]))*(sta[top-1].x-sta[top].x)
                >=(f(sta[top-1])-f(sta[top]))*(now.x-sta[top].x))top--;
            sta[++top]=now;
            n+=k;
        }
        else
        {
            int b;
            read(b,k);
            sumk+=k,sumb+=b;
        }
        while(top>1&&f(sta[top])>=f(sta[top-1]))top--;
        printf("%lld %lld\n",sta[top].x+1,f(sta[top]));
    }
    return 0;
}