P4513 小白逛公园
求区间的最大子段和。一眼线段树题。那么我们考虑对于线段树的每个节点应该怎么维护：
对于每个节点，额外设几个变量：sum, ml, mr, ms, 分别表示区间和、包含左端点的最大子段和，包含右端点的最大子段和，最大子段和。
我们用p1, p2来表示左儿子和右儿子。
ms的维护：
-
当最大子段和只在左边的区间时，ms = p1.ms;
-
当最大子段和只在右边的区间时，ms = p2.ms;
-
当最大子段和为中间的一段连续区间时： ms = p1.mr + p2.ml;
三者取最大值即可。
ml的维护：
-
ml只在左边区间时: ml = p1.ml;
-
ml的范围延续到了右边区间: ml = p1.sum + p2.ml;
两者取最大值。
mr的维护同理。
然后码就完了。(于是就码了一个多小时）
P7706 「Wdsr-2.7」文文的摄影布置
同样一眼线段树题。首先我们肯定能迅速求出 \(\min_{i < j < k} \left \{ B_j \right \}\) 。我们要想办法求出 \(\psi(i, k)\) 了。 \(\psi(i, k) = A_i + A_k - min(B_j)\) 。我们自然是不能直接暴力枚举 \(i, j, k\) 的，肯定会T到飞起。那么可以怎么做呢？作为一个线段树题，我们肯定会先考虑对于线段树节点 \(p\) , 维护 \(\psi (p)\) 。记节点 \(p\) 的左儿子为 \(p1\) ， 右儿子为 \(p2\) 。
我们试着考虑 \(i, k\) 的位置。
-
首先，若 \(i, k\) 均在左儿子或右儿子区间中，这种情况非常简单，直接就是 $\psi (p) = max(\psi(p1) , \psi(p2)) $
-
其次，便是稍微困难的 \(i\) 在左儿子区间， \(k\) 在右儿子区间中了。我们对 \(j\) 的位置分类讨论一下: 当 \(j\) 在左边时， 我们可以发现， \(A_k\) 必然取右边区间的最大值。这时，我们只需要求左边的 \(max(A_i - B_j)\) 了。于是将这2个加入维护的值中。分别记为 \(P\) , \(Q\) , 之后就非常简单了。