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\) , 之后就非常简单了。