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

数据结构

线性数据结构

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

两个队列，一个存原数，另一个存合并后的数，每次取出两个队头比较，选出大的。初始桶排插入队列。

P2827 [NOIP2016 提高组] 蚯蚓

三个队列，分别存原数和分开的两部分。变长用 $Delta$ 维护，每次把 $Delta$ 加上 $q$，把不加的两条再减去 $q$

并查集

P1197 [JSOI2008] 星球大战

把删边操作存储下来，倒序加边，并查集维护。

（要注意读题，求的是****未被占领****的连通块个数）

P2391 白雪皑皑

维护并查集，让还没染色的点指向 $0$，其他点与其后的第一个没染色的点在同一个并查集内。

优化：以 $\log n$ 为大小分块（只能维护一维的并查集）（我不会）。

线段树

要注意维护的内容、标记的内容和高效的维护方式。

P3373 【模板】线段树 2

打过四遍的板子，注意懒惰标记pushdown的处理，还有要先乘再加。

P4513 小白逛公园

线段树维护区间最大子段和，还需要维护每个区间的最大前缀和、最大后缀和以及区间和。维护时划分中线，$pre$、$ans$ 和 $suf$ 都可以在一边或在两边。

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

$ans$ 三元组有四种情况，在左右区间或仅一个在左右区间。

因此要维护区间内一个差的最大值，维护两种此类二元组时也要分成在区间同一侧和两侧的情况讨论。

（多元组可以分成多个低元组维护，可能用背包）

P1471 方差

做过，当时是因为一个double写成int调了一个小时。

推式子以后维护区间和以及区间平方和求解即可。

P6327 区间加区间 sin 和

维护区间和，区间 $sin$ 和以及区间 $cos$ 和，用和差角公式（我没学）维护求解。

P5278 算术天才⑨与等差数列

有以下条件：

• 最大值和最小值之差等于公差乘项数-1；
• 所有数模 $k$ 相等（用区间gcd维护）
• 无重复数字（用 $pre_i$ 表示前面第一个与它相同的来判断，因此对每个值维护一个set存储它出现的下标，用lower_bound）

反正没听懂。

P6617 查找 Search

没听。

Codechef DGCD（弱化版）

难点在标记对信息的修改。

将原来 $a$ 数组的gcd转化为差分数组的gcd， 则转化成单点修改+区间gcd，方便处理。

T367829 软萌甜心小仙女

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

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

CF280D k-Maximum Subsequence Sum

反悔贪心，黑题没听。

学长讲解：反悔贪心时取反，区间乘 $-1$，如此取 $k$ 次，每次更新答案。

乘 $-1$ 时相当于把最大变为最小，因此同时维护区间、前缀、后缀的最大最小值，乘 $-1$ 以后转换一下即可。听懂了还是不想写

P3215 [HNOI2011] 括号修复 / [JSOI2011]括号序列

• 简化版，去掉swap操作。

在调题，没听。

P4036 [JSOI2008] 火星人

• 简化版，去掉插入操作。

线段树维护区间哈希值，预处理出 $base$ 的若干次方。

询问时二分答案，变为判断两个区间是否相等

经典问题

题意：区间除以 $x$ 下取整，求区间和。

没咋听懂，好像要使数变为 $0$，原因和实现方式均没懂。

P4145 上帝造题的七分钟 2 / 花神游历各国

与上题一样，要使数变为 $1$，同样没听懂。

CF438D The Child and Sequence

看这个题的题解全明白了qwq。

对于某些线段树无法区间维护的运算，若对某个数只需操作很少的次数就不再改变（如除以一个数、取模的 $\log n$ 次和开平方的 $\log \log n$ 次），可以直接一down到底暴力修改，同时维护区间最大值。

当区间最大值已低于不会被改变的值（如除以的 $0$、开平方的 $1$、取模的模数） 时就不再操作，如此时间复杂度可以接受。

该性质称为复杂度均摊。

HDU 6315 Naive Operations

一个结论：

$\sum_{i=1}^{n} \frac{1}{i}=O(\log n)$

后边没听到，应该听了也不会。

P9989 [Ynoi Easy Round 2023] TEST_69

没听。

LOJ504 ZQC的手办

也没听。