CF671E Organizing a Race

题意

Link_Luogu

Link_Codeforces

题解

单调栈，线段树二分，其实也可以看成是线段树形的单调栈，具体看 LGOJ4198 楼房重建

首先考虑没有 限制的情况，如何判断 可不可以办比赛，我们设第 个加油站的油量为 ，第 到 之间的道路长度为 。

我们再设 ，

显然充要条件为 且

现在多出了 个扩大 的机会，考虑在满足 能到达 的情况下，尽可能的把加油站往后放。我们设 ，那么 形成一棵每个点只有 or 个儿子的多条链形结构。对于一个起点 ，沿着链向下一直走，设经过的点为 ，其中 ，最优方案显然为 ，剩余的 中没有用掉的部分肯定全部堆在 上最有可能成功，易知 。

我么设 为 被修改之后的 的值，显然如果我们只走到 ， ，然后修改 相当于把 的 都增加， 端特殊处理一下。

然后就是单调栈维护 了，在单调栈被修改的之后维护 ，然后线段树二分 的合法最大值。然而这只线段树解决了从 走到 ，所以还要先在单调栈中二分出最远能从 走到的地方，之后再在这个范围内线段树二分。

代码

#include <bits/stdc++.h>

using namespace std;

namespace IO {
    const int SIZE = 1 << 20;
    char buf[SIZE + 10], *iS, *iT;
    inline char Getc() {
        return iS == iT && (iT = (iS = buf) + fread(buf, 1, SIZE, stdin), iS == iT) ? EOF : *iS++;
    }
    template <class TT>
    inline void Read(TT &x) {
        x = 0; register char cc = '\0'; TT fff = 1;
        for (; cc < '0' || cc > '9'; cc = Getc())
            if (cc == '-') fff = -1;
        for (; cc >= '0' && cc <= '9'; cc = Getc())
            x = (x << 1) + (x << 3) + (cc & 15);
        x *= fff;
    }
}
using IO::Read;

typedef long long LL;

const int N = 1e5 + 10;

int n, K, fans, Top, Stack[N], a[N], b[N];
LL f[N], g[N];

namespace Seg {
    #define lc (x << 1)
    #define rc (x << 1 | 1)

    LL Tree[N * 4 + 10], Original[N * 4 + 10], Lazy[N * 4 + 10];
    inline void Pushup(int x) { if (x) Tree[x] = max(Tree[lc], Tree[rc]); }
    inline void Pushdown(int x) {
        if (!Lazy[x]) return;
        Lazy[lc] += Lazy[x], Tree[lc] += Lazy[x];
        Lazy[rc] += Lazy[x], Tree[rc] += Lazy[x];
        Lazy[x] = 0;
    }
    void Build(LL *A, int x = 1, int nl = 1, int nr = n) {
        if (nl == nr) {
            Tree[x] = Original[x] = A[nl];
            return;
        }
        int nm = (nl + nr) >> 1;
        Build(A, lc, nl, nm), Build(A, rc, nm + 1, nr);
        Original[x] = max(Original[lc], Original[rc]), Pushup(x);
    }
    void Update(int el, int er, LL ad, int x = 1, int nl = 1, int nr = n) {
        if (el <= nl && nr <= er) {
            Tree[x] += ad, Lazy[x] += ad;
            return;
        }
        int nm = (nl + nr) >> 1;
        Pushdown(x);
        if (el <= nm) Update(el, er, ad, lc, nl, nm);
        if (er > nm) Update(el, er, ad, rc, nm + 1, nr);
        Pushup(x);
    }
    int wantx, wantnl, wantnr;
    LL premaxh, wantmaxh;
    int FinalFind(int x, int nl, int nr, LL lim) {
        if (nl == nr) {
            // if (lim <= Tree[x] + K)
            /* FinalFind 的每一步都保证了下一层有解，上面的那个就没必要了  */
            return nr;
        }
        int nm = (nl + nr) >> 1;
        Pushdown(x);
        if (max(lim, Tree[lc]) <= Original[rc] + K) {
            /* 易知此时右边必有一可行解（不一定最优），不必递归左边，上面条件也是冲要的 */
            /* 有的题目右边不一定存在可行解这里要加上 findans = nm!!! */
            return FinalFind(rc, nm + 1, nr, max(lim, Tree[lc]));
        }
        return FinalFind(lc, nl, nm, lim);
    }
    void PreFind(int el, int er, int x = 1, int nl = 1, int nr = n) {
        if (el <= nl && nr <= er) {
            if (premaxh <= Original[x] + K)
                wantmaxh = premaxh, wantx = x, wantnl = nl, wantnr = nr;
            premaxh = max(premaxh, Tree[x]);
            return;
        }
        int nm = (nl + nr) >> 1;
        Pushdown(x);
        if (el <= nm)
            PreFind(el, er, lc, nl, nm);
        if (er > nm)
            PreFind(el, er, rc, nm + 1, nr);
    }
    LL Query(int ed, int x = 1, int nl = 1, int nr = n) {
        if (nl == nr) return Tree[x];
        int nm = (nl + nr) >> 1;
        Pushdown(x);
        if (ed <= nm) return Query(ed, lc, nl, nm);
        else return Query(ed, rc, nm + 1, nr);
    }

    #undef lc
    #undef rc
} // namespace Seg

int main()
{
    freopen("CF671E.in", "r", stdin);
    freopen("CF671E.out", "w", stdout);

    Read(n), Read(K);
    for (int i = 1; i < n; ++i)
        Read(b[i]);
    for (int i = 1; i <= n; ++i)
        Read(a[i]);

    f[0] = f[1] = g[0] = g[1] = 0;
    for (int i = 2; i <= n; ++i) {
        f[i] = f[i - 1] + (a[i - 1] - b[i - 1]);
        g[i] = g[i - 1] + (a[i] - b[i - 1]);
    }
    Seg::Build(g);
    Stack[++Top] = n, fans = 1;
    for (int i = n - 1; i >= 1; --i) {
        while (Top > 0 && f[Stack[Top]] >= f[i]) {
            if (Top != 1)
                Seg::Update(Stack[Top - 1] - 1, n, -(f[Stack[Top]] - f[Stack[Top - 1]]));
            --Top;
        }
        if (Top != 0)
            Seg::Update(Stack[Top] - 1, n, f[i] - f[Stack[Top]]);
        Stack[++Top] = i;
        int L = 1, R = Top, mid = 0, fps = n + 1;
        while (L <= R) {
            mid = (L + R) >> 1;
            if (f[i] - f[Stack[mid]] > K) fps = Stack[mid], L = mid + 1;
            else R = mid - 1;
        }
        Seg::premaxh = Seg::wantmaxh = -0x3f3f3f3f3f3f3f3fLL;
        Seg::wantx = 1, Seg::wantnl = 1, Seg::wantnr = n;
        Seg::PreFind(i, fps - 1);
        int rightpos = Seg::FinalFind(Seg::wantx, Seg::wantnl, Seg::wantnr, Seg::wantmaxh);

//        fprintf(stderr, "%d : %d\n", i, rightpos);    
//        printf(" : %d %d %lld : %d \n", Seg::wantnl, Seg::wantnr, Seg::wantmaxh, rightpos);

        fans = max(fans, rightpos - i + 1);
    }
    printf("%d\n", fans);

    return 0;
}