CF671E Organizing a Race（线段树维护前缀最值+贪心）

木xx木大 · 2021-07-06 21:16:02 · 题解

CF671E Organizing a Race

分别设 pre[i],suf[i] 表示从 1 到 i 和从 i 到 1 和要花费多少油，有

pre[i]=pre[i-1]-g[i-1]+w[i-1]\\ suf[i]=suf[i-1]-g[i]+w[i-1]

则从 i 向右走到 j 所花的油量为 pre[j]-pre[i]，从 j 向左走到 i 所花的油量为 suf[j]-suf[i]。设 w(l,r) 表示在[l,r] 这个区间至少给 g 增加多少才可以往返通行。当 w(l,r)\le k 时这个区间可以作为答案。

首先考虑从 l 走到 r 至少需要多少油，当存在一个 i 满足 pre[i]-pre[l]>0 时 l 无法走到 i 。记右边第一个这样的 i 为 nxt[l]，设 val[i]=pre[nxt[i]]-pre[i] 表示至少给 g 增加多少 i 才能走到 nxt[i]。这些增加的油放在 [i,nxt[i]) 中的任何一个位置对于去程来说都是等价的，但为了让回程尽可能走远，我们将新增的油放在 nxt[i]-1 的位置是最优的。这样更新后 l 走到 nxt[l] 时剩余的油量为 0，就可以接着解决 nxt[l]\to r 的子问题了。这样处理完后就可以算出 cost(l,r) 表示 l\to r 的最小代价了。

下面就只需要让 r 能到 l 了，显然如果要增加的话把新增的油全部放在 r 处一定是最优的。我们需要求出需要增加多少。刚刚从左到右的过程对 g 有影响（g[nxt[i]-1]+=val[i]），相应地，suf 也会受到影响。记被影响后的新的 suf 为 suf'。r 无法回到 l 当且仅当存在一个 i\in[l,r] 满足 suf'[i]<suf'[r]，记 minsuf'(l,r)=\min\limits_{i=l}^{r-1}suf'[i]（注意这个区间是左闭右开的）， r 处增加的值即为 \max(0,suf'[r]-minsuf'(l,r))。那么 w(l,r)=cost(l,r)+\max(0,suf'[r]-minsuf'(l,r))。满足 w(l,r)\le k 即满足 cost(l,r)\le k 且 cost(l,r)+suf'[r]-minsuf'(l,r)\le k。

考虑对于每个 l 最多能向右走到哪里。首先，对于一个固定的 l ，cost(l,r) 是关于 r 递增的函数，可以先二分处一个上界 rmax。考虑一个 S=\{nxt[l],nxt[nxt[l]]\dots\} 的链状结构， S 中的每一个元素 x，会对 cost(l,r) 产生一个后缀加的影响（从 x 开始的后缀），同时会对 suf'[r] 产生一个后缀减的影响（从 x 开始的后缀）。我们发现，这两者的贡献可以完全抵消掉！换句话说，cost(l,r)+suf'[r] 恒等于 suf[r]！最后，对于 minsuf'(l,r)，x 会对 suf' 产生一个后缀减的影响（从 x-1 开始的后缀）

那么，对于每个固定的 l ，位置 r 的代价为 suf[r]-minsuf'(l,r)。其中，minsuf'(l,r)=\min\limits_{i=l}^{r-1}suf'[i]。这个 i\ge l 的限制不好处理，在处理某个特定的 l 时，可以把 suf'[1,l-1] 加上 INF，这样就化为了 \min\limits_{i=1}^{r-1}suf'[i]。其中 r\le rmax ，类似地，可以把 suf'[rmax+1,n] 减去 INF 来保证合法。

现在问题转化为了维护 c_i=a_i-\min\limits_{j=1}^{i} b_j的最小值，支持 b 的区间加，查询 c_i\le k 的 i 的最大值。可以用维护前缀最值信息的线段树维护。具体地，线段树上每个节点维护 \min \{a_i\},\min \{b_i\}和仅考虑这个区间时右子树的答案 ans。对于修改操作，直接给 b 加，给 ans 减并打 tag 。对于 pushup 操作，用一个类似楼房重建的每次向一边递归的函数维护当前节点信息

对于查询操作，一般情况下可以直接线段树上二分，但这里略有不同。考虑一个 query(ro,x) 操作，表示前缀最小值为 x 时 c_i\le k 的 i 的最大值

bmi_{ls}<x$ 时，$x$ 不影响右区间，那么 $ans_{ro}\le k$ 时向右子树递归，否则向左子树递归，时间复杂度为 $O(\log n)
bmi_{ls}\ge x$ 时，左子树完全被 $x$ 控制了。先向右子树递归，如果有合法的直接 return；否则在左子树中查$a_i-x\le k$ 的最大的 $i$ ，移项得 $a_i\le k+x$，这就是一个经典的线段树上二分了。因为最多进行 $O(\log n)$ 次线段树上二分，总复杂度为$O(\log^2n)


#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
namespace FGF
{
    const int N=1e5+5;
    const ll INF=0x3f3f3f3f3f3f3f3f;
    int g[N],w[N],n,m,nxt[N],st[N],ans=1,tp;
    struct tree{
        ll ans,ami,bmi,ta;
    }t[N<<2];
    ll pre[N],suf[N];
    vector<int> G[N];
    void add(int ro,ll x){t[ro].bmi+=x,t[ro].ans-=x,t[ro].ta+=x;}
    void pushdown(int ro){if(t[ro].ta)add(ro<<1,t[ro].ta),add(ro<<1|1,t[ro].ta),t[ro].ta=0;}
    ll pushup(int ro,int l,int r,ll p)
    {
        if(l==r)return t[ro].ami-p;
        pushdown(ro);
        return t[ro<<1].bmi<p?min(pushup(ro<<1,l,mid,p),t[ro].ans):min(t[ro<<1].ami-p,pushup(ro<<1|1,mid+1,r,p));
    }
    void build(int ro,int l,int r)
    {
        if(l==r){t[ro].ami=t[ro].bmi=suf[l];return;}
        build(ro<<1,l,mid),build(ro<<1|1,mid+1,r);
        t[ro].ans=pushup(ro<<1|1,mid+1,r,t[ro<<1].bmi);
        t[ro].ami=min(t[ro<<1].ami,t[ro<<1|1].ami),t[ro].bmi=min(t[ro<<1].bmi,t[ro<<1|1].bmi);
    }
    void updat(int ro,int l,int r,int L,int R,ll x)
    {
        if(L<=l&&r<=R)return add(ro,x);
        pushdown(ro);
        if(L<=mid)updat(ro<<1,l,mid,L,R,x);
        if(R>mid)updat(ro<<1|1,mid+1,r,L,R,x);
        t[ro].bmi=min(t[ro<<1].bmi,t[ro<<1|1].bmi);
        t[ro].ans=pushup(ro<<1|1,mid+1,r,t[ro<<1].bmi);
    }
    int query2(int ro,int l,int r,ll x)
    {
        if(l==r)return l;
        return t[ro<<1|1].ami<=x?query2(ro<<1|1,mid+1,r,x):query2(ro<<1,l,mid,x);
    }
    int query(int ro,int l,int r,ll &x)
    {
        if(l==r)
        {
            int tmp=t[ro].ami-x<=m?l:0;
            x=min(x,t[ro].bmi);
            return tmp;
        }
        pushdown(ro);
        if(x>t[ro<<1].bmi)
        {
            if(t[ro].ans<=m)return query(ro<<1|1,mid+1,r,x=t[ro<<1].bmi);
            int tmp=query(ro<<1,l,mid,x);
            x=min(x,t[ro].bmi);
            return tmp;
        }
        else 
        {
            int tmp=(t[ro<<1].ami<=m+x?query2(ro<<1,l,mid,m+x):0);
            return max(tmp,query(ro<<1|1,mid+1,r,x));
        }
    }
    void dfs(int u)
    {
        if(nxt[u]<=n)updat(1,1,n,nxt[u]-1,n,pre[u]-pre[nxt[u]]);
        if(u<=n)
        {
            int l=2,r=tp,s=1;ll x=INF; 
            while(l<=r)pre[st[mid]]-pre[u]>m?(s=mid,l=mid+1):r=mid-1;
            if(u>1)updat(1,1,n,1,u-1,INF);
            updat(1,1,n,st[s]-1,n,-INF);
            ans=max(ans,query(1,1,n,x)-u+1);
            if(u>1)updat(1,1,n,1,u-1,-INF);
            updat(1,1,n,st[s]-1,n,INF);
        }
        st[++tp]=u;
        for(auto v:G[u])dfs(v);
        if(nxt[u]<=n)updat(1,1,n,nxt[u]-1,n,pre[nxt[u]]-pre[u]);
        tp--;
    }
    void work()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<n;i++)
            scanf("%d",&w[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&g[i]);
        for(int i=2;i<=n;i++)
            pre[i]=pre[i-1]+w[i-1]-g[i-1],suf[i]=suf[i-1]+w[i-1]-g[i];
        for(int i=1;i<=n;i++)
            nxt[i]=n+1;
        for(int i=n;i;i--)
        {
            while(tp&&pre[st[tp]]<=pre[i])tp--;
            if(tp)nxt[i]=st[tp];
            st[++tp]=i;
            G[nxt[i]].push_back(i);
        }
        build(1,1,n);
        tp=0;
        dfs(n+1);
        printf("%d\n",ans);
    }
}
int main()
{
    FGF::work();
    return 0;
}