洛谷秋令营Day3-数据结构

堆、并查集（不用启发式合并就可以）、树状数组和线段树（仅限区间加、乘、赋值、求和和最值）、字典树（S 组唯一处理多字符串的结构）、STL set/map/multiset

目前流行的考法是用数据结构优化一些基本信息的维护。

二叉堆

P8755，每台机器维护一个堆，堆以已经接收任务的截止时间为键，然后直接模拟即可，及时弹出已经做完的任务。

P12247，沿着时间轴 DP，用一个结构维护可能选的值，结构里需要能及时删除过期的元素（或懒惰删除），并维护元素的最大值

P2048，维护得非常机智的一个题目，紫题被当场降到黄题，5 年降一次

并查集

无向图的连通性问题

P11005，最大边权的最小值，感觉要 MST，求出 MST 之后，考虑求 <= R 和 <= L - 1 的路径有多少，减一下就好了。给的做法是，kruskal 加边，使得 (u, v) 第一次联通时，加入的边的边权就是这两个点对之间的花费。假如花费在 [L, R] 之间，考虑联通时两个集合的大小，相乘就是这条边的贡献次数了。

P1967，询问两个点之间权值的最大值，多倍经验： 蓝桥杯 2023 省 A] 网络稳定性 - 洛谷

P9565，越与越小，与至多变化 log 次，无向图，能拆位吗？对 w 拆位，第 i 位为 1 则在第 i 个图里连边，k 是固定的，>= k 只有至多 60 种情况，相当于建 60 个图，每个图代表一种更大的比 k 大的前缀，把这个前缀的 1 被包含的边都加进去。

P8026，不会。需要用启发式合并而不是路径压缩？

树状数组

P3801，初始全都是 0，标记每行/每列是否被翻转过，则为了求矩阵中 1 的个数，只要 1 配 0 和 0 配 1 就好了

线段树

P8473，题意没看明白呢。。。

P3792，哈希题？类似这个F - Rearrange Query，看起来重排哈希是一个很常用的技巧了。

P5524，操作，每次执行第 l 到 r 个操作，询问独立。某次查询的值一定是之前赋值时的值。有点太困难了。

Trie

P2536，把 n 个串建成一个 trie，然后在树上游走，通配符的话，问号直接把指针全部下推到直接儿子，星号则指针全部下推到这个子树里所有点。朴素做法可以 dp 看前 i 位和前 j 位能不能匹配上。

P13630，相当于一次删除字典树的一个大小不超过 k 的子树，可以指定根结点。直接 trie 上 dfs，遇到一个点，假如 sz <= k 就删了，否则 dfs 其子树，看怎么删，但 dfs 子树的顺序是什么？万一可以连带着自己一起删呢？

P6018，无根树转有根树，后边不会了，似乎太困难了。