【题解】[CF671E] Organizing a Race

有 $n$ 个点依次排成一列,第 $i$ 个点与第 $i + 1$ 个点之间的距离为 $w_i$ 个单位。第 $i$ 个点有一个加油站,可以给你的车加能跑 $g_i$ 个单位的油。

你需要在 $l, r$ 之间往返($l \le r$),也就是说,要满足一辆没有油的车能从 $l$ 一路向右开到 $r$,也能从 $r$ 一路向左开到 $l$。车会在起点加好油,你可以在中途加油,但是方向是不能改变的。你可以假设车的油箱是无限大的。

你还没选好 $l, r$ 的具体取值,不过你希望让你经过的点数尽量多,也就是让 $r - l + 1$ 尽量大。

你现在有 $k$ 个机会,每个机会可以将任意一个 $g_i$ 增加 $1$。问:使用 $k$ 次机会后,能得到的最大的 $r - l + 1$ 是多少?

这题十分的神…所以也难怪 $4$ 年前的题目会被选入今年的集训队作业。

做这题,那必然就是看题解…这题难点由两部分,「转化成抽象模型」和「用线段树维护」,比较神奇的是这题里这两部分几乎同等难度,并且都是我难以望见的高度…

接下来应该不太会做这种难度的题了。感觉很不好。虽然这题确实十分的好,新颖有趣且经典,但我还是驾驭不了这种题目吧…

XXXXXXXXXXXX 正文 XXXXXXXXXXXX

首先考虑,对于一段区间而言,需要多少操作多少次,才能保证正着走完并且反着走完。那么也就是需要算出正着走和反着走都需要额外的多少代价。

这个地方有个贪心。考虑定「向右走」为正方向。那么假设从 $i$ 开始走,如果遇到某个 $j>i$ 发现走不得,那么应该在何处加油?因为还要考虑反着走回来,所以必然是加在最靠右的地方最优,所以就会选择的在 $j-1$ 处加油。记 $i$ 向右走遇到的第一个这样的 $j$ 为 $stop_i$ 。

于是根据这个贪心就可以求出 $need(i,j)$ ,表示从 $i$ 走到 $j$ 需要多少代价。但这样也是只是保证了正着可以走。不妨令 $p_{i}$ 表示从 $1$ 走到 $i$ 花费的油量,$q_i$ 表示从 $i$ 走到 $1$ 花费的油量。 那么可知有递推:

那么可以知道,在走 $i\to j$ 这条路线时,同时也在进行对

这些位置进行单点加,那么对 $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$ ,本质上是在维护这么一个式子:

首先变一下形:

这样做的正确性在于,只要每次将 $<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$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
#include <map>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std ;

#define fr firsr
#define sc second

#define ls (rt << 1)
#define rs (rt << 1 | 1)

#define to(k) E[k].to
#define val(k) E[k].val
#define next(k) E[k].next

#define il inline

#define rg register

typedef double db ;

typedef long long ll ;

typedef vector<int> vint ;

typedef map<int, int> mint ;

const db eps = 1e-7 ;

const int N = 200010 ;

const int M = 200010 ;

const ll Inf = (1ll << 60) ;

const ll Fni = -(1ll << 60);

il int qr(){
int r = 0, f = 1 ;
char c = getchar() ;
while (c > '9' || c < '0'){
if (c == '-') f = -1 ; c = getchar() ;
}
while (c <= '9' && c >= '0'){
r = (r << 1) + (r << 3) + c - '0', c = getchar() ;
}
return r * f ;
}

template <typename T>

void debug(T *const tp, int minn, int maxn, char v = ' ', char c = '\n'){
for (int i = minn ; i <= maxn ; ++ i) cout << tp[i] << v ; cout << c ;
}
int cnt ;
int head[N] ;
struct Edge{
int to ;
int val ;
int next ;
}E[N * 2] ;

void add_e(int x, int y, int w = 0){
to(++ cnt) = y ; val(cnt) = w ;
next(cnt) = head[x] ; head[x] = cnt ;
}
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

int res ;
int top ;
ll sp[N] ;
ll ss[N] ;
int n, m ;
int w[N] ;
int g[N] ;
int fa[N] ;
int stk[N] ;

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(ls, l, mid, v) ;
return ask(rs, mid + 1, r, 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 = sb[ls] ;
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)) ;
}
}

void dfs(int x){
stk[++ top] = x ;
if (fa[x] <= n)
update(1, 1, n, fa[x] - 1, n, - sp[fa[x]] + sp[x]) ;
if (x <= n){
int l = 2, r = top - 1, ans = 1, mid ;
while (l <= r){
mid = (l + r) >> 1 ;
if (sp[stk[mid]] - sp[x] > m)
ans = mid, l = mid + 1 ; else r = mid - 1 ;
}
ll tmp = Inf ; ans = stk[ans] - 1 ;
if (x > 1) update(1, 1, n, 1, x - 1, Inf) ;
if (ans <= n) update(1, 1, n, ans, n, Fni) ;
res = max(res, query(1, 1, n, tmp) - x + 1) ;
if (x > 1) update(1, 1, n, 1, x - 1, Fni) ;
if (ans <= n) update(1, 1, n, ans, n, Inf) ;
}
for (int k = head[x] ; k ; k = next(k)) dfs(to(k)) ;
stk[top --] = 0 ;
if (fa[x] <= n)
update(1, 1, n, fa[x] - 1, n, sp[fa[x]] - sp[x]) ;
}
int main(){
cin >> n >> m ; w[n] = Inf ;
for (int i = 1 ; i < n ; ++ i) w[i] = qr() ;
for (int i = 1 ; i <= n ; ++ i) g[i] = qr() ;
for (int i = 2 ; i <= n ; ++ i){
sp[i] = sp[i - 1] - g[i - 1] + w[i - 1] ;
ss[i] = ss[i - 1] - g[i] + w[i - 1] ;
}
stk[++ top] = n + 1 ;
sp[n + 1] = Inf ; fa[n + 1] = n + 1 ;
for (int i = n ; i >= 1 ; -- i){
while (top && sp[stk[top]] <= sp[i]) -- top ;
fa[i] = stk[top] ; stk[++ top] = i ;
}
for (int i = 1 ; i <= n ; ++ i) add_e(fa[i], i) ;
build(1, 1, n) ; top = 0 ; dfs(n + 1) ;
cout << res << '\n' ; return 0 ;
}s