xht37 的洛谷博客

xht37's blog:https://www.xht37.com/

题解 CF671E 【Organizing a Race】

CF671E Organizing a Race

题意

  • 有 $n$ 个点排成一行,第 $i$ 个点与第 $i + 1$ 个点之间的距离为 $w_i$ 个单位。
  • 每个点都有一个加油站,第 $i$ 个点的加油站可以给你的车加能跑 $g_i$ 个单位的油。
  • 若一辆初始没有油的车能从 $l$ 一路向右开到 $r$,也能从 $r$ 一路向左开到 $l$,则称 $l,r$ 之间可以往返。
  • 另外,你有 $k$ 次将某个 $g_i$ 加 $1$ 的机会。
  • 请你求出在 $l,r$ 之间可以往返的情况下, $r-l+1$ 的最大值。
  • $n \le 10^5$, $k,w_i,g_i \le 10^9$。

题解

考虑什么条件下 $l,r$ 之间可以往返。

显然为: $$\begin{cases}w_l \le g_l \\w_l + w_{l+1} \le g_l + g_{l+1} \\\cdots \\\sum_{i=l}^{r-1} w_i \le \sum_{i=l}^{r-1} g_i\end{cases}$$ 以及 $$\begin{cases}w_{r-1} \le g_r \\w_{r-1} + w_{r-2} \le g_r + g_{r-1} \\\cdots \\\sum_{i=l}^{r-1} w_i \le \sum_{i=l+1}^{r} g_i\end{cases}$$ 考虑对 $w,g$ 的前缀和 $a,b$,则条件变为: $$\begin{cases}a_l-a_{l-1} \le b_l-b_{l-1} \\a_{l+1}-a_{l-1} \le b_{l+1}-b_{l-1} \\\cdots \\a_{r-1}-a_{l-1} \le b_{r-1}-b_{l-1}\end{cases}$$ 以及 $$\begin{cases}a_{r-1} - a_{r-2} \le b_r - b_{r-1} \\a_{r-1} - a_{r-3} \le b_r - b_{r-2} \\\cdots \\a_{r-1} - a_{l-1} \le b_r - b_{l}\end{cases}$$ 设 $c_i = a_{i-1} - b_{i-1}$, $d_i = b_i - a_{i-1}$,则条件变为简单的两个等式: $$\begin{cases}c_{l} = \max_{i=l}^{r} c_i\\d_{r} = \max_{i=l}^{r} d_i\end{cases}$$ 若 $g_i$ 加 $1$,则对于 $j \ge i$, $b_j$ 加 $1$;对于 $j > i$, $c_j$ 减 $1$;对于 $j \ge i$, $d_j$ 加 $1$。

先考虑 $l \to r$。

从 $n$ 到 $1$ 枚举 $l$,用单调栈维护一个单调上升的子序列 $c_{x_0} < c_{x_1} < c_{x_2} < \cdots$,其中 $x_0 = l$。则 $k$ 一定是贪心地依次对 $g_{x_1-1},g_{x_2-1},\cdots$ 使用,每次将 $g_{x_i-1}$ 加 $c_{x_i} - c_{x_{i-1}}$。

再考虑 $r\to l$。

到某个 $x_p$ 后,设剩下的 $k$ 为 $k^\prime$,上一步使用完后的 $d$ 为 $d^\prime$,则要满足 $d^\prime_r + k^\prime \ge d^\prime_{l \dots r-1}$,即 $d_r + k \ge \max_{i=l}^{r-1} d^\prime_{i}$。

因此,我们可以先在单调栈上二分出只考虑 $l \to r$ 的情况下的最大 $r^\prime$,即找到满足 $c_{x_i} - c_{l} \le k$ 的最大 $x_i$,则最大 $r^\prime = x_{i+1} - 1$。

此时,最优解的范围一定在 $[l,r^\prime]$ 中,再在这个范围内的线段树上二分找到最大的 $r$,然后取每次 $r-l+1$ 的最大值即可。

具体来说,我们用线段树维护 $d^\prime$,每次往单调栈里加一个位置 $x$ 后,将单调栈中前一个位置 $y$ 的贡献 $c_{y} - c_{x}$ 加到 $d^\prime_{y-1\dots n}$ 上,退栈时相应减去。另外,对于 $l$ 左边的部分,为了方便可以将 $d^\prime$ 设为 $-\infty$。

线段树上二分时,对于一个节点 $p$,如果 $\max_{rs} d_i + k \ge \max_{1\dots p_{mid}} d^\prime_i$,则意味着 $\max_{rs} d_i$ 的 $i$ 处一定是一个合法解,因此递归往右儿子找,否则递归往左儿子找。

为什么 $\max_{rs} d_i + k \ge \max_{1\dots p_{mid}} d^\prime_i$ 就意味着 $\max_{rs} d_i$ 的 $i$ 处一定是一个合法解呢?合法条件为 $d_r + k \ge \max_{i=l}^{r-1} d^\prime_{i}$,那么 $d^\prime_{p_{mid+1}\dots i-1}$ 中有没有可能比 $d_i + k$ 大呢?

其实很显然,注意到 $d^\prime$ 是 $d$ 加上 $\le k$ 的一个数生成的就可以了。

时间复杂度 $\mathcal O(n \log n)$。

代码

const int N = 1e5 + 7;
const ll inf = 1e18;
int n, ans, s[N], p;
ll k, w[N], g[N], a[N], b[N], c[N], d[N];
struct T {
    int l, r;
    ll x, z, d;
} t[N<<2];

void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r, t[p].x = -inf;
    if (t[p].l == t[p].r) return;
    build(ls, l, md), build(rs, md + 1, r);
}

inline void upd(int p) {
    t[p].x = max(t[ls].x, t[rs].x);
    t[p].d = max(t[ls].d, t[rs].d);
}

inline void spd(int p) {
    if (t[p].z) {
        t[ls].x += t[p].z;
        t[ls].z += t[p].z;
        t[rs].x += t[p].z;
        t[rs].z += t[p].z;
        t[p].z = 0;
    }
}

void setx(int p, int x, ll k) {
    if (t[p].l == t[p].r)
        return t[p].x = t[p].d = k, void();
    spd(p);
    if (x <= md) setx(ls, x, k);
    else setx(rs, x, k);
    upd(p);
}

void add(int p, int l, int r, ll k) {
    if (t[p].l >= l && t[p].r <= r)
        return t[p].x += k, t[p].z += k, void();
    spd(p);
    if (l <= md) add(ls, l, r, k);
    if (r > md) add(rs, l, r, k);
    upd(p);
}

int ask(int p, int l, int r, ll x) {
    if (t[p].l == t[p].r) return t[p].l;
    spd(p);
    if (md < l) return ask(rs, l, r, x);
    if (r <= md) return ask(ls, l, r, x);
    if (t[rs].d + k >= max(x, t[ls].x))
        return ask(rs, l, r, max(x, t[ls].x));
    return ask(ls, l, r, x);
}

int main() {
    rd(n), rd(k), rda(w, n - 1), rda(g, n);
    for (int i = 1; i < n; i++) a[i] = a[i-1] + w[i];
    for (int i = 1; i <= n; i++) b[i] = b[i-1] + g[i];
    for (int i = 1; i <= n; i++) c[i] = a[i-1] - b[i-1];
    for (int i = 1; i <= n; i++) d[i] = b[i] - a[i-1];
    build(1, 1, n);
    for (int i = n; i; i--) {
        while (p && c[i] >= c[s[p]]) {
            if (p > 1)
                add(1, s[p-1] - 1, n, c[s[p]] - c[s[p-1]]);
            --p;
        }
        s[++p] = i, setx(1, i, d[i]);
        if (p > 1) add(1, s[p-1] - 1, n, c[s[p-1]] - c[i]);
        int l = 1, r = p;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (c[s[mid]] - c[i] <= k) r = mid;
            else l = mid + 1;
        }
        r = r == 1 ? n : s[r-1] - 1;
        ans = max(ans, ask(1, i, r, -inf) - i + 1);
    }
    print(ans);
    return 0;
}

2020-03-16 02:25:16 in 题解