CF2019(div2,vp)

比赛时网站炸了两次，有一次甚至连那个 Oops 的页面都没看到。/fn

D. Speedbreaker

做法比较多的一题。
首先有一个带 log 但是比较简单的做法。求出 \(a\) 的后缀 min \(s_i\) 和前缀 min \(p_i\)，当出发点为 \(x\) 时，设

则 \(x\) 可行当且仅当对于每一个 \(j\)，\(\leq j\) 的 \(b_i\) 数量不超过 \(j\)。事实上这是一个经典结论。然后用线段树维护就行了。

另一个与这个做法类似的线性做法是，将对于每个点判定转化为判定有哪些点，
即可行的点 \(x\) 满足将 \(a_i\) 改为 \(1\) 后，包含所有 \(a_i\leq j\) 的点的最小子区间 \([l_j,r_j]\) 的长度不超过 \(j\)，
这样对于每个 \(j\)，可以得到可行的 \(x\) 一定在 \([r_j-j+1,l_j+j-1]\) 中，取一下交集就行了。