【学习记录】24.02.16 数据结构
KSCD_
·
·
个人记录
数据结构
线性数据结构
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」文文的摄影布置
因此要维护区间内一个差的最大值，维护两种此类二元组时也要分成在区间同一侧和两侧的情况讨论。
（多元组可以分成多个低元组维护，可能用背包）
### 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的手办
也没听。