题解 P6780

dead_X · 2022-09-15 08:46:43 · 题解

将序列以长度为 C 分块，那么答案要么在一块里面，要么是一块后缀加一块前缀。

一块里面的很好算，就是对这个区间求最大子段和。

一块后缀加一块前缀比较难算，记 A_i 为这一块后 i 个数的和，B_i 为下一块前 i 个数的和，我们要实现一个直角三角形区域的最大值查询：

问题转化为 A 数组后缀加，B 数组后缀加，全局所有点最大值。

看到这种等腰直角三角形求值的套路，首先可以通过这种方式来做：

即将三角形拆成两个更小的三角形，然后中间转为矩形求解，矩形求解可以根据两个三角形的信息反推。

看到这个结构就不难想到线段树了吧，我们对于每个节点维护横向最大值，纵向最大值，三角形最大值，合并是平凡的。

于是这样 A 数组和 B 数组的区间修改就可以用带懒标记的线段树做了。

我们递归到线段树上对应这几个区间的节点，将三角形最大值和横向/竖向最大值加上 t，然后再把信息合并起来即可。

Corner case 是一块只能取最后若干个，另一块只能取最前若干个。

我们也能拆成若干个询问，所以这题做完了。

时间复杂度 O(m\log n)，比较卡常，如果不想卡常可以去 gym 上交，如果被卡常了可以洗洗脸多交几发。

一些卡常小技巧：

• 能 build 就不要一个一个 update，把 n\log n 尽可能消掉。
• 线段树不用开到 4n，可以计算一个上界。
• 对于 merge 比较慢的信息，可以单侧递归直接返回就单侧递归。
• 快读快写可能没什么用。
• 开 inline 有用。
• 少开 long long 有用。

要代码私聊。