教义问答手册 题解 挺简单的一道二分。 首先看到题目首先应该很容易想到dp，毕竟用dp求这个最大值应该是很简单的。 但是由于询问太多，我们不可能对每个询问都做一次dp，考虑整体二分。 对于二分时，我们处理掉所有当前的过 m i d mid mid的询问。 可以通过分别求出左边的dp值与右边的dp值来计算。 由于涉及到合并的问题，我们的状态 d p i , j dp_{i,j} dpi,j​分