Atcoder Beginner Contest 408
By pan_g
(Atcoder ID : GjyBilly)
To commemorate the thirty-sixth all do ABC.
A Timeout
看看 $T_{i + 1} - T_i$ 与 $S$ 的关系，如果有 $i$ 满足 $S < T_{i + 1} - T_i$ 则为 No ，但是注意时间点是从 $0$ 开始，所以 $T_1$ 要特判。
B Compression
就是离散化操作，非常简单，排序 + 去重即可。
C Not All Covered
考虑从最薄弱的墙突破，因为只要破一面墙就好了。
由于每个塔楼会保护住一个区间的墙，所以这个区间内的墙想突破必须打破这个塔楼，所以就是一个区间加的操作。
所以可以差分，再前缀和，取 $\min$ 即可。
D Flip to Gather
记 $C(l, r)$ 为这个区间的 1 的个数，可以用前缀和算得，前缀和数组记为 $S$ 。
考虑对区间 $[l, r]$ 置为全 1 ，其他全 0 的操作数，应该为
$$ C(1, l - 1) + (r - l + 1) - C(l, r) + C(r + 1, N) $$
用前缀和数组表示就是
$$ 2S_{l - 1} - (l - 1) - (2S_r - r) + S_N $$
那么就是对于 $\{2S_n - n\}$ 这个序列 $A$ ，找到最大的 $A_r - A_{l - 1}$ ，再用上面的公式找答案即可。
时间复杂度 $O(N)$ 。
E Minimum OR Path
唯独没想到贪心的一集
考虑从最高为开始扫，第 $k$ 位能不为 $1$ 就不为 $1$ ，所以就是一个贪心。
从 OR 的性质入手，将第 $k$ 位为 $1$ 的没有被删掉的边暂时删掉，如果 $1$ 和 $N$ 的连通性能保证，说明第 $k$ 为可以不为 $1$ ，此时把暂时删掉的边永远的删掉就好了。
时间复杂度 $O(M \log w)$ 。
F Athletic
直接连边不太现实，不太确定线段树优化建图有没有可行方案，果断想别的思路。
因为 $H$ 在移动的过程中是递减的，所以可以考虑好好利用这个性质。
又观察到 $H$ 是个排列，无疑又增添了便利，考虑把 $H^{-1}$ 拿出来，于是就变成了一个 DP 。
记 $f_i$ 表示在高度为 $i$ 时能移动的最高次数
$$ f_i = \max_{1\leq j \leq i - D \wedge |H^{-1}_j - H^{-1}_i| \leq R}\{f_j\} + 1 $$
这个东西显然可以基于 $H^{-1}$ 权值线段树优化，甚至不用可持久化。
时间复杂度 $O(N\log N)$ 。
G A/B < p/q < C/D
但凡小学奥数学好点
小学奥数并没有教会我太多，所以不会 G 过于正常。
考虑对于两个假分数 $\dfrac AB$ 与 $\dfrac CD$ ，我们可能会觉得它烦，所以直接减到真分数。
如果 $\dfrac AB$ 与 $\dfrac CD$ 一真一假，那我们就找到了 $q = 1$ ；但如果都是真分数，我们可能就束手无策了。
所以怎么变呢，考虑取倒数，变成
$$ \dfrac DC < \dfrac qp < \dfrac BA $$
欸？这不就变成两个假分数了吗？接下来，迭代即可。
但是我们还没处理一个问题，那就是这样得到的 $q$ 真的最小吗？
那我们只要解决取倒数的操作是否合理即可。
已知如果 $q$ 要变小，那么 $p$ 也会相对应的变小，当 $p$ 取小时， $q$ 也会自然取小，那我们的终止条件取的就是最小的 $\dfrac 11$ ，所以得到的结果一定是最优的。
