题解

思路

固定一个候选高度 $H$，把高度不低于 $H$ 的木板记为一，否则记为零。询问可放置高度至少为 $H$，当且仅当区间 $[l,r]$ 内存在长度至少为 $w$ 的连续一段。随着 $H$ 降低，满足条件的位置只会增加，因此具有单调性。

做法

将不同高度从大到小排序，依次激活对应位置。用可持久化线段树保存每个高度处理完后的状态；节点维护区间长度、最长全一前缀、最长全一后缀和最长连续一段。合并两个节点时，跨越中点的候选长度等于左后缀加右前缀。

对每个询问，在高度版本上二分。查询某个版本的 $[l,r]$，若其中最长连续一段不少于 $w$，则该高度可行。取最高的可行高度即为答案。

小规模可以对每个询问用单调队列求所有长度为 $w$ 的窗口最小值并取最大。若所有询问均有 $w=1$，答案就是区间最大值，可用普通线段树或稀疏表查询。

复杂度

建立全部版本耗时和空间均为 $O(n\log n)$；每个询问二分高度并查询线段树，耗时 $O(\log^2 n)$。

正确性证明

在高度版本 $H$ 中，位置为一恰好表示对应木板能够承载高度为 $H$ 的标志。宽度为 $w$ 的标志能够完全放入询问区间，当且仅当其中存在至少 $w$ 块连续可承载木板，这又恰好等价于线段树返回的最长连续一段不少于 $w$。降低高度只会激活更多位置，所以可行性单调。二分得到的最高可行版本对应的高度因此正是最大答案。