CF1137E 题解

· · 题解

重要的条件是每次加入的直线，斜率和截距全都是正数。

哦，那不就是永远第一个点最小值吗？不不不可能前后插入0进来，emmmm。

如果前面插入0，那么后面之前的点不就都没用了吧，可是当后面插入0的时候事情好像就稍微复杂一点……

直线……线性……最优性问题……这一类的条件很容易扯到凸包上面去，我们来推导一番。

结论：不在当前局面由所有点(x-1,A_x)（x代表序列中第x个点）（x-1是因为题目中的直线就是s(i-1)+b）构成的下凸壳的那些点，永远不是最小值。

首先不在凸壳上意味着在当前局面就不是最小值，我们要证明的就是在之后加入一些直线后他也不会是最小值。

如图，其中1号点和3号点在凸壳上，2号点不在凸壳上，并且有A_3<A_2<A_1。

我们现在想要加入一条直线，使得3号点的值增加，并且还要使2号点成为最小值。A_3+kx_3+b>A_2+kx_2+b，那么

k>\frac {A_2-A_3}{x_3-x_2}

由于凸壳的性质，我们知道1号点和2号点直线的斜率是大于2号点和3号点直线的斜率的，也就是

\frac {A_3-A_2}{x_3-x_2}<\frac {A_2-A_1}{x_2-x_1}

换一下符号发现

k>\frac {A_2-A_3}{x_3-x_2}>\frac {A_1-A_2}{x_2-x_1}

即A_2+kx_2>A_1+kx_1，所以我们发现这时候2号点的值已经大于1号点了，不可能是最小值。 (以后碰到线性问题就瞎猜凸包)。

那么我们就只需要维护一个下凸壳就行了：

操作1：前面加入一个点下凸壳清空。

操作2：后面加入一个点，不停地从凸壳尾部弹点。

操作3：全体加上一条直线………好像有点麻烦？对于这个操作我们单独维护一个全局标记(k,b)表示每个点的值应该是存储的值加上这个标记的值。如在数组里面存的点是(x,y)，实际上它的值是(x,y+kx+b)。那么进行第3个操作的时候就是增加标记。同时注意第一个操作清空凸包也清空标记，第2个操作为了让加入的点的纵坐标是0，初始的权值是(x,-(kx+b))。

代码（膜拜yybyyb，借鉴了dalao的代码思路）：

#include<cstdio>
#define N 1023000
#define ll long long
#define double long double
const double eps=1e-6;
struct Point{
    ll x,y;
    Point (ll _x=0,ll _y=0) : x(_x),y(_y) {}
    Point operator - (const Point &B) const {return Point(x-B.x,y-B.y);}
    double operator * (const Point &B) const {return (double)x*B.y-(double)y*B.x;}
}stk[N];
int top;ll k,b;
ll calc(Point A) {return A.y+k*A.x+b;}
inline int read(){
    int n=0;char a;bool z=false;
    while(a=getchar())
    {
        if (a>'9'||a<'0')
            if (z) break;
            else continue;
        if (!z) z=true;
        n=(n<<3)+(n<<1)+(a^48);
    }
    return n;
}
int main()
{
    ll n=read();int Q=read(),opt;Point now;
    stk[top=1]=Point();
    while(Q--)
    {
        opt=read();
        switch(opt)
        {
            case 1:stk[top=1]=Point();n+=read();k=b=0;break;
            case 2:now=Point(n,-(n*k+b));n+=read();
                while(top>1&&(now-stk[top-1])*(stk[top]-stk[top-1])>-eps) --top;
                stk[++top]=now;break;
            case 3:b+=read();k+=read();break;
        }
        while(top>1&&calc(stk[top])>=calc(stk[top-1])) --top;
        printf("%lld %lld\n",stk[top].x+1,calc(stk[top]));
    }
    return 0;
}

//by qlwpc