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;
}
全部评论

相关推荐

点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务