【CF1137E】Train Car Selection | Mrsrz's blog

想法，维护下凸壳

题目大意：

给定一个数列，初始有 $n$ 个 $0$。有 $m$ 个操作，为以下三种：

1. 在最前面插入 $k$ 个 $0$。
2. 在最后面插入 $k$ 个 $0$。
3. 给定 $b,s$，对于所有的数，令第 $i$ 个数增加 $b+s(i-1)$。

每次操作完毕后，输出数列中的最小值，以及第一次出现的位置。

题解：

由于增加的 $b,s$ 是正数，所以一段相同的数，能成为最小值的只有可能是第一个数。

那么，在前面插入 $0$ 的操作，我们可以把其他所有数全部扔掉，只保留一个 $0$，因为无论怎么变化，第一个现在为 $0$ 的数始终小于等于后面的数。

在后面插入 $0$ 的操作，我们也只需要插入一个 $0$ 即可。

考虑数列中能成为最小值的数，这个非常套路，把位置当做横坐标，值当做纵坐标，在下凸壳上的点才有可能成为最小值。

那么我们用栈维护下凸壳即可。

全局的加法可以维护两个全局变量实现。

那么这是一个 $O(m)$ 的算法。

Code：

#include<iostream>
#include<utility>
using namespace std;
typedef long long LL;
int n,m,top;
LL h,t,B,S;
pair<LL,int>sta[300005];
inline LL get(pair<LL,int>x){return x.first+B+(x.second-1)*S;}
inline bool cross(pair<LL,int>a,pair<LL,int>b,pair<LL,int>c){
#define x first
#define y second
    a.x-=c.x,a.y-=c.y;
    b.x-=c.x,b.y-=c.y;
    return 1.*a.x/b.x>=1.*a.y/b.y;
#undef x
#undef y
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    h=0,t=n;
    sta[top=1]=make_pair(0,1);
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int k;
            cin>>k;
            top=1;
            B=S=0;
            h+=k;
            sta[1]=make_pair(0,1);
        }else
            if(op==2){
                int k;
                cin>>k;
                if(get(sta[top])>0){
                    pair<LL,int>p=make_pair(-B-S*(h+t),h+t+1);
                    while(top&&cross(p,sta[top],sta[top-1]))--top;
                    sta[++top]=p;
                }
                t+=k;
            }else{
                int b,s;
                cin>>b>>s;
                B+=b,S+=s;
                while(top>1&&get(sta[top])>=get(sta[top-1]))--top;
            }
//        for(int i=1;i<=top;++i)
//            cout<<get(sta[i])<<' '<<sta[i].second<<';';
//        cout<<endl;
        cout<<sta[top].second<<' '<<get(sta[top])<<'\n';

    }
    return 0;
}