1873F

CF1873F Money Trees 双指针好题，但是我用的队列（ 考虑先找出所有极长的、满足任意一个数都能被它后面的那个数整除的连续段。显然这个操作可以在 \(\mathcal{O}(n)\) 的时间复杂度内完成。 求出每个极长连续段的答案，取 \(\max\) 即为最终答案。那么现在的问题就是 ......

思路 要求最长长度，想到可以二分答案。 那么现在需要考虑如何快速验证答案是否正确。 可以 \(O(n)\) 枚举区间左端点，因为有了长度，所以可以直接获得右端点的值，直接验证右端点是否合法。 因为要求区间的每个数都是右边的数的倍数，所以可以提前预处理每个点最远的满足这个条件的右端点，直接判断合不合法 ......

二分+前缀和。 要求使得区间和小于 \(k\) 的子区间长度，显然可以二分处理。二分区间长度，枚举区间左端点，check 两项内容：区间是否合法（符合 \(h_i \mod h_{i+1}=0\) ），区间和是否小于 \(k\)。对于当前区间长度，只要有一个区间满足条件，即返回真。 区间和可以通过前 ......