2.16

· · 个人记录

大佬博客

P6033 [NOIP2004 提高组] 合并果子 加强版

两个队列，一个存合并前的（有序），一个合并后每次取每个队列的前两个进行合并

P2827 [NOIP2016 提高组] 蚯蚓

单调队列维护最长

然后同上题，维护切开操作(两段分别放在两个队列)

维护dleta，先 +q ，然后给切出来两段的减去 q

P1197 [JSOI2008] 星球大战

把删除想成修建

P2391 白雪皑皑

P3373 【模板】线段树 2

P4513 小白逛公园

单点改，区间查，线段树

维护两个儿子的最大子段和、最大前缀和最大后缀，维护自己的最大子段和

P7706 「Wdsr-2.7」文文的摄影布置

P6327 区间加区间 sin 和

维护区间和，区间 sin 和以及区间 cos 和，用和差角公式维护求解

T367829 软萌甜心小仙女

结论：答案长度不大于 3（因为大于 3 的分开后必有一段平均数不小于原来的平均数）

所以只需要考虑区间内长度为 2 和 3 的区间平均数即可，维护区间两个平均数以及区间首尾长度 1 和 2 的区间和即可。

k-Maximum Subsequence Sum

反悔贪心

反悔贪心时取反，区间乘 −1，如此取 k 次，每次更新答案。

乘 −1 时相当于把最大变为最小，因此同时维护区间、前缀、后缀的最大最小值，乘 -1 以后转换一下即可。