千篇一律的矩形数点看腻了？来点纯的 DS 做法。

前置知识：ST 表，单调队列。

和题目一致，用 $k_i$ 表示当前询问下 $i$ 的答案。

利用特殊性质，由此能够导出两个优化的方向。

解法 1

考虑特殊性质 $D$：$L_j> \frac{2}{n}$。

特殊性质 D $O(nq)/O(nq+n\log n)$

在分治方向上思考，不难发现，特殊性质等价于：任意合法的区间一定经过序列的中点。

标记序列中点 $mid$，对于序列左半边的一个点 $i$，不难发现，设 $f_j$ 表示以 $j$ 为左端点的最大权值合法区间 $[j,r]$，只需要满足 $j\le i$，则一定有 $j\le i\le mid< r$。

所以说，对于左半侧的位置 $i$ 的答案，只需要对于每个 $j\in [1,mid]$ 求出对应的 $f_j$，则 $k_i=\max_{j\le i}f_j$。

求出 $f_j$ 可以用滑动窗口（或者 ST 表，后者常数应该更小），$k_i$ 直接统计前缀最大值，比较容易可以做到 $O(nq)/O(n\log n+nq)$。

一般情况 $O(nq\log n)$

考虑拓展这个做法：

上述做法中，我们不关注合法区间的长度，所需要的条件只是合法区间必须经过序列中点。

考虑分治，对于当前分治区间，只保留经过区间中点的合法区间，没经过的则丢到两边分别做分治，每个分治区间里都做一遍上述算法，可以做到复杂度 $O(nq\log n)$。

根据常数可以获得 $50\sim 70$ 分不等。

一般情况 $O(nq+n\log^2 n)$

继续优化：

对于区间 $[l,r]$，处理询问 $[L,R]$，有一些显然的事实：

1. 计算 $[l,r]$ 经过中点的代价为 $O(\min(R,r-l+1))$。

2. 若 $r-l+1<L$，则区间没有计算和分治的必要。

设最大的 $\frac{n}{2^t}\le L$，则根据事实一，分治最大进行到第 $t$ 层。分治的区间个数量级为 $\sum_{h=0}^t 2^h \approx 2^{t+1}> \frac{n}{L}$。

根据事实二，我们分治算法的时间复杂度的一个下界为 $O\left(qn\frac{R}{L}\right)$。

看出来了什么？当 $R,L$ 之间的比值太大时，复杂度中 $qn$ 的系数退化就会变成 $\log n$，这是我们不希望的。我们希望的是 $O\left(\frac{R}{L}\right)\approx O(1)$。

另外一个显然的事实：对于询问 $[L,R]$，可以拆成 $[L,p],[p+1,R]$ 两个询问来处理。

考虑这样一种倍增分块的方法：对于 $t\in [0,\log n)$，我们将 $R-L+1\le [2^t,2^{t+1})$ 分为一块，只有 $\log$ 块，合法区间长度在这些块的询问可以预处理！

对于一次询问，考虑去掉中间的整块部分，剩下的散块一定满足存在一个 $t$，使得 $2^t\le L\le R< 2^{t+1}$，这样的散块直接做分治的复杂度就是 $O(n)$！

预处理做 $O(\log n)$ 次分治，然后预处理 $G_{i,j,k}$ 表示询问长度在 $i\sim j$ 块内位置 $k$ 的答案，这一部分可以做到 $O(n\log^2 n)$。

每次查询，整块直接统计答案，散块直接做两个线性的分治，复杂度为 $O(nq)$。

于是我们在 $O(n\log^2 n+nq)$ 的复杂度内解决这个问题，虽然常数比较大，但这种线性分治的思想非常巧妙。

解法 2

这次变换视角，我们根据特殊性质 D 转化出一个关键的条件：$2L_j>R_j$。

特殊性质 D $O(nq)/O(nq+n\log n)$

观察这个条件，可以注意到另外一个关键的结论：对于覆盖 $i$ 的最优合法区间 $[l,r]$，一定有 $i$ 到左右两个端点的最小距离一定不超过 $L$。

对于 $k_i$，考虑枚举一个和 $i$ 距离不超过 $L$ 的左端点 $j$，计算以 $f_j$ 为左端点的最大合法区间 $[j,r]$，因为 $r-j>L,i-j<L$，所以一定有 $i\le r$。

因此覆盖 $i$ 的最优区间左端点距离 $i$ 不超过 $L$ 的情况考虑过了，答案为 $f_j$ 的一个长度为 $L$ 的区间的最大值。

对于左端点的情况考虑过了，右端点也可以同样处理一个 $g_j$，答案为：

$$k_i=\max\left(\max_{i-L<j\le i}f_j,\max_{i\le j< i+L}g_j\right)$$

$f_i,g_i$ 是两个滑动窗口，而 $k_i$ 的求解也是两个滑动窗口。可以用 ST 表套单调队列或者纯单调队列轻松做到 $O(n\log n+nq)/O(nq)$。

一般情况 $O(nq+n\log^2 n)$

考虑拓展这个做法：

上述条件的核心结论是，$2L_j>R_j$，如果询问不满足这个性质怎么办？

把这个结论写成一个必要的形式，即存在 $t$ 满足 $2^t\le L\le R< 2^{t+1}$。即可满足上面的性质。

不满足？还是预处理，倍增分块，对于散块预处理需要的询问，合法区间长度在 $[2^k,2^{k+1})$，满足上面需要的性质。需要预处理 $\log$ 次，然后同理预处理出 $G_{i,j,k}$，复杂度为 $O(n\log^2 n)$。

对于询问，整块直接套用预处理的结果，散块的两个询问一定满足 $2^t\le L\le R< 2^{t+1}$，直接用上面的做法做就行了。复杂度为 $O(nq)$。

于是，我们用另外一种方法在 $O(n\log^2 n+nq)$ 的复杂度解决了这个问题。

结语

我们用两种看似不同的做法，得出了两个十分相似的解决问题的结构，这就是 DS 的有趣之处。

关于代码编写的意见，对于滑动窗口问题，ST 表的常数要远小于单调队列，但只能在预处理好的序列上做，单调队列虽然常数大，但是确不需要预处理，编码时可以酌情考虑合适的算法。