本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-16 10:51:22

大佬博客

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$ 以后转换一下即可。