题解 CF671E 【Organizing a Race】

orz 兔，兔是我们的红太阳，我们不能没有他！ 这边只是稍微详细地讲了讲转化后线段树该如何实现。前面的推导只是提供一个前情提要（ 顺便增加了一点自己的个人理解。 _____ 首先考虑，对于一段区间而言，需要多少操作多少次，才能保证正着走完并且反着走完。那么也就是需要算出正着走和反着走都需要额外的多少代价。 这个地方有个贪心。考虑定「向右走」为正方向。那么假设从 $i$ 开始走，如果遇到某个 $j>i$ 发现走不得，那么应该在何处加油？因为还要考虑反着走回来，所以必然是加在最靠右的地方最优，所以就会选择的在 $j-1$ 处加油。记 $i$ 向右走遇到的第一个这样的 $j$ 为 $stop_i$ 。 于是根据这个贪心就可以求出 $need(i,j)$ ，表示从 $i$ 走到 $j$ 需要多少代价。但这样也是只是保证了正着可以走。不妨令 $p_{i}$ 表示从 $1$ 走到 $i$ 花费的油量，$q_i$ 表示从 $i$ 走到 $1$ 花费的油量。 那么可知有递推： $$ p_i=p_{i-1}+g_{i-1}-w_{i-1}$$ $$q_i=q_{i-1}+g_{i-1}-w_i $$ 那么可以知道，在走 $i\to j$ 这条路线时，同时也在进行对 $$g_{stop_i},g_{stop_{stop_i}},g_{stop_{stop_{stop_i}}}\cdots$$ 这些位置进行单点加，那么对 $q$ 的影响就是一个后缀加。记后缀加完之后的 $\{q_n\}$ 为 $\{\tau_n\}$ 。则如果不能从 $j$ 回到 $i$ ，就意味着着存在一个 $i\leq k<j$ ，使得 $q_{k}-q_{j}<0$ 。怎么量化这个东西呢？考虑还是贪心，如果从 $j$ 到 $i$ 走不了，那么一定会要把贡献累加到 $j$ 上，那需要累加的量就是 $q_{j}-\min_{k=i}^{j-1}\{q_{k}\}$ 。这也就是如果想要 $[i,j]$ 这个区间变得合法的最小贡献。 考虑如何计算这个东西。比较暴力的解法那必然是枚举一个左端点，然后向右走更新右端点。这样是 $n^2$ 的。发现如果想要优化，只能选择加速寻找右端点这个过程。但是有个问题在于，对于固定的 $i$ ，和想要二分出的 $j'$，要经过不同的 $stop$ 集合，同时有着不同的 $q_{j'}-\min_{k=i}^{j'-1}\{q_{k}\}$ ，求一次是 $O(n)$ 的，反而把复杂度搞成了 $n^2\log n$ 。 分开考虑这两点。对于经过不同 $stop$ 集合这个问题，可以继续深入挖掘性质。发现对于一个 $j$，可能存在一个连续段 $[k_1,k_2]$ 满足 $\forall z\in[k_1,k_2]\cap\mathbb{Z_+}$ ，$stop_z=j$ 。这种一对多的逻辑结构不难想到要用森林去表征。那么这个问题比较好解决了。建出一棵森林 $T$ ，连边 $i\leftrightarrow stop_i$ 。再建立一个虚根 $root$ ，与所有 $stop_i$ 未定义的结点相连。这样只要从 $root$ 开始 dfs，用退栈的方式辅助二分即可快速修改。 对于第二点，考虑对于一个固定的 $i$ ，本质上是在维护这么一个式子： $$t_{j'}=q_{j'}-\min_{k=i}^{j'}\{\tau_k \}$$ 首先变一下形： $$t_{j'}=q_{j'}-\min_{k=1}^{j'}\{\tau_k \}$$ 这样做的正确性在于，只要每次将 $<i$ 的那些 $k$ 的 $\tau_k$ 都置为 $+\infty$ 就可以了。 考虑到底要怎么维护这个东西。发现在查询的过程中，需要单点修改 $g_i$ ，那么也就是区间修改 $q_j$ 和 $\tau_k$ ，那么也就是说要支持：1、维护前缀最小值 2、区间加/减 3、查询出某个最小值的位置。那自然就是线段树了。 考虑后一半的前缀最小值，因为带上修改比较麻烦，所以维护起来依然要选择楼房重建的方式，拿左区间的最小值去二分右区间的前缀。于是可以比较简单地维护出一个区间的 $\min\{t_i\}$ 。 考虑修改。修改的话就是暴力打标记，注意到 $t_i$ 中的 $\tau_k$ 是负贡献，被 $\min$ 套着，但由于是区间修改所以可以直接减。 考虑如何查询。询问比较麻烦，因为相当于查询时要合并多个区间的单调栈，所以无法直接线段树二分。或者说，需要魔改一下二分，让这个二分可以「边二分，边合并」。 考虑一种比较神秘的方式去找。`query(root, l, r, val)` 查询的是区间 $[1,l-1]$ 内某个数 `val`，作为前缀最小值对区间 $[l,r]$ 有影响时，最靠右的 $\leq m$ 的位置。那么考虑分类： 1、如果当前左孩子区间的 $\min\{\tau_k\}$ 比 $val$ 要小，说明当前的前缀最小值不会对右区间产生影响(因为左右区间已经合并了)，那么就可以直接判断在算上左区间对右区间贡献时，右区间 $t$ 的最小值是否 $\leq m$ —— 这就是比较朴素的线段树上二分 —— 如果是的话就应该去右儿子里面找，否则去左儿子里找。 2、如果当前左孩子区间的 $\min\{\tau_k\}$ 比 $val$ 要大，说明左区间对右区间产生的贡献会被 $val$ 产生的贡献代替，所以直接递归进右孩子。并且由于 $val$ 已经变成了当前左区间的前缀最小值，所以左区间的 $\min\{\tau_k\}$ 就变成了无用信息(因为肯定都比 $val$ 大)，只需要查询在 $q_i+val\leq m$ 时的最大下标即可，这一部分可以直接线段树二分。 但…这似乎也不是最终的查询。考虑为了让最后的 $\min_{k=1}^{j'}\{\tau_k\}$ 真的变成从 $1$ 开始到 $i$ 结束的最小值， 所以需要动态修改 $val$ 的值。先序遍历线段树即可。当然也可以直接维护一个前缀最小 $\tau_k$ 。 这里就只给出线段树部分的代码吧，其他部分比较简单： ```cpp ll s[N * 3] ; ll sa[N * 3] ; ll sb[N * 3] ; ll tag[N * 3] ; void _down(int rt, int l, int r){ if (tag[rt]){ s[ls] -= tag[rt] ; s[rs] -= tag[rt] ; sb[ls] += tag[rt] ; sb[rs] += tag[rt] ; tag[ls] += tag[rt] ; tag[rs] += tag[rt] ; tag[rt] = 0 ; } } ll solve(int rt ,int l, int r, ll v){ if (l == r) return sa[rt] - v ; int mid = (l + r) >> 1 ; _down(rt, l, r) ; if (sb[ls] < v) return min(solve(ls, l, mid, v), s[rt]) ; else return min(solve(rs, mid + 1, r, v), sa[ls] - v) ; } void build(int rt, int l, int r){ if (l == r) return void(sa[rt] = sb[rt] = ss[l]) ; int mid = (l + r) >> 1 ; build(ls, l, mid) ; build(rs, mid + 1, r) ; sa[rt] = min(sa[ls], sa[rs]) ; sb[rt] = min(sb[ls], sb[rs]) ; s[rt] = solve(rs, mid + 1, r, sb[ls]) ; } void update(int rt, int l, int r, int ul, int ur, ll v){ if (ul <= l && r <= ur){ tag[rt] += v ; sb[rt] += v ; s[rt] -= v ; //1 return ; } _down(rt, l, r) ; int mid = (l + r) >> 1 ; if (ul <= mid) update(ls, l, mid, ul, ur, v) ; if (ur > mid) update(rs, mid + 1, r, ul, ur, v) ; sb[rt] = min(sb[ls], sb[rs]) ; s[rt] = solve(rs, mid + 1, r, sb[ls]) ; } int ask(int rt, int l, int r, ll v){ if (l == r) return l ; int mid = (l + r) >> 1 ; if (sa[rs] <= v) return ask(rs, mid + 1, r, v) ; else return ask(ls, l, mid, v) ; } int query(int rt, int l, int r, ll &v){ if (l == r){ int ret ; ret = sa[rt] - v <= m ? l : 0 ; v = min(v, sb[rt]) ; return ret ; } int mid = (l + r) >> 1 ; _down(rt, l, r) ; if (sb[ls] <= v){ if (s[rt] <= m){ v = min(sb[ls], v) ; return query(rs, mid + 1, r, v) ; } else { int ret ; ret = query(ls, l, mid, v) ; v = min(v, sb[rt]) ; return ret ; } } else { int ret = 0 ; if (sa[rt] - v <= m) ret = ask(ls, l, mid, m + v) ; return max(ret, query(rs, mid + 1, r, v)) ; } } ```