人类在哪里

NATO · 2025-12-01 15:25:00 · 题解

很简单的做法，可惜场上没时间搞 O(nq) 了。

考虑特殊性质 D 的做法。

考虑枚举区间的左端点 i\in[1,n-l+1]，对于每个 i 有可能的右端点 [i+l-1,\min(n,i+r-1)]。

注意到对于 j\in[i,i+l-1] 这一部分 i 为左端点的贡献必然是最优的，也就是 [i+l-1,\min(n,i+r-1)] 中前缀和最大的值减去 i-1 的前缀和。

对每个 i 求出这个最优值 val_i 后你再做一个长度为 l 的滑动窗口（[j-l+1,j] 中 val 的最大值）即可把所有 i 对 j 的贡献算上。

类似于 l，你同样可以枚举 r 算这样一个贡献。

你发现对于一个 j，你必然把所有满足它作为一个区间左端点及之后不超过 l 个数或右端点及之前不超过 l 个数的区间都贡献上了。

也即是长度为 [l,2l-1] 的区间必然已经贡献过了！

上述过程均可以在预处理 ST 表后 O(n) 完成。

你发现你实现了 l 翻倍，即 O(nq) 的 D 性质。

你还可以得到一个普适性的 O(n\log n+nq\log n) 的做法（l 翻倍不超过 \log n 次）且是符合除 C 以外特殊性质的做法，期望得分 65。