P10196 [USACO24FEB] Lazy Cow P 题解

考虑如果从 (t_1,y_1) 到 (t_2,y_2) 如何最优，因为每分钟代价是指数，显然越平均越好，除一下模一下即可简单计算。再考虑三个 t 单增的点 (t_{1,2,3},y_{1,2,3}) 如何分配最优，如果这三个点上凸，那显然直接 1,2 一段，2,3 一段更优，否则可以证明直接走 1,3 在最优的同时也满足了 (t_2,y_2) 的限制。

可以归纳说明我们分的段一定在当前点集的上凸壳上，只需要 set 维护动态加点上凸壳即可，每次删除一段点之后撤销贡献再加入该点两端贡献即可。代码细节非常多。复杂度均摊 O(n\log n)。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define int long long
#define mod 1000000007
using namespace std;

int n,ans;
set <pair <int,int>> st;

inline int calc(int x,int k){
    if(k<0) return 0;
    k%=(mod-1);
    int tmp=1;
    while(k){
        if(k&1) tmp=tmp*x%mod;
        x=x*x%mod;
        k>>=1;
    }
    return tmp;
}

inline void in(int &n){
    n=0;
    char c=getchar();
    while(c<'0' || c>'9') c=getchar();
    while(c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
    return ;
}

inline int val(int x,int y){
    int xx=x/y,md=x%y;
    return (calc(3,xx)*md%mod+calc(3,xx-1)*(y-md)%mod)%mod;
}

inline double K(int x,int y,int xx,int yy){return x==xx?1e9:1.*(y-yy)/(x-xx);}

signed main(){
    in(n);
    st.insert({0,0});
    int x,y;
    in(x),in(y);
    st.insert({x,y});
    ans=val(y,x);
    printf("%lld\n",ans);
    for(int i=2;i<=n;i++){
        int x,y;
        in(x),in(y);
        auto rt=st.lower_bound({x,0});
        auto lf=prev(rt);
        if((*lf).second>=y||(rt!=st.end()&&(*rt).first==x&&(*rt).second>=y)){
            printf("%lld\n",ans);
            continue;
        }
        while(rt!=st.end()&&(*rt).second<=y) rt++;
        if(rt==st.end()){
            while(lf!=st.begin()){
                int x1=(*lf).first,y1=(*lf).second;
                int x2=(*prev(lf)).first,y2=(*prev(lf)).second;
                if(K(x,y,x1,y1)>K(x1,y1,x2,y2)) lf--;
                else break;
            }
            auto it=next(lf);
            while(it!=st.end()){
                auto tmp=*prev(it);
                (ans+=mod-val((*it).second-tmp.second,(*it).first-tmp.first))%=mod;
                it++;
            }
            (ans+=val(y-(*lf).second,x-(*lf).first))%=mod;
            st.erase(next(lf),st.end());
            st.insert({x,y});
            printf("%lld\n",ans);
            continue;
        }
        while(next(rt)!=st.end()){
            int x1=(*rt).first,y1=(*rt).second;
            int x2=(*next(rt)).first,y2=(*next(rt)).second;
            if(K(x1,y1,x2,y2)>K(x,y,x1,y1)) rt++;
            else break;
        }
        while(lf!=st.begin()){
            int x1=(*lf).first,y1=(*lf).second;
            int x2=(*prev(lf)).first,y2=(*prev(lf)).second;
            if(K(x,y,x1,y1)>K(x1,y1,x2,y2)) lf--;
            else break;
        }
        auto it=next(lf);
        while(prev(it)!=rt){
            auto tmp=*prev(it);
            (ans+=mod-val((*it).second-tmp.second,(*it).first-tmp.first))%=mod;
            it++;
        }
        int x1=(*lf).first,y1=(*lf).second;
        int x2=(*rt).first,y2=(*rt).second;
        if(K(x1,y1,x2,y2)<K(x1,y1,x,y)){
            (ans+=val(y-y1,x-x1))%=mod;
            (ans+=val(y2-y,x2-x))%=mod;
            st.erase(next(lf),rt);
            st.insert({x,y});
        }
        else (ans+=val(y2-y1,x2-x1))%=mod;
        printf("%lld\n",ans);
    }

    return 0;
}