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

相关推荐

就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务