Atcoder vp记录

\(1.\) AtCoder Beginner Contest 435
\(Rank\)：\(2300\)，赛时：\(ABCDE\)，补题：\(F\)
总结：纯区，C题细节写错两次，D题想不到暴力+写错一次，E题颜色段均摊不会写，F第一不会写st表，第二不开long long，已经完全不是人类了。
简单说下F：
策略是对当前可达区间拆为去左边最大值和右边最大值两种子情况然后递归，用st表O(1)计算最大值位置，每个位置作为最大值贡献一次，故复杂度最多O(n)，总复杂度为O(nlogn)，瓶颈在st表预处理。
考虑正确性。首先，由于被拆后无法通行，故一定是跳到当前最大值左边或右边，不存在左右横跳的情况。
设当前整个区间最大值位置为pos1，pos1左侧最大值位置为pos2，pos1右侧最大值位置为pos3。
若跳到的位置既不是pos2，也不是pos3，那么一定需要将这两者提前拆除。
此时<pos2与>pos3的位置均无法抵达，而就左侧而言，从pos1跳到一个(pos2, pos1)的位置pos4，贡献一定不如先跳到pos2再删pos2跳到pos4，右侧同理。
故一定是pos1跳到pos2或pos3，直接分治下去即可。