2022 UESTC ICPC Training for Data Structures
A
首先对于每个物品,连续整除 d,匹配到能打开的最小钥匙。在钥匙编号从大到小排序后,可以
接下来问题转化为区间不同颜色数查询。由于
需要注意的是, __builtin_popcount
仅接受 32 位的输入, 使用 64 位整形时应使用 __builtin_popcountll
.
B
线段树区间加法、区间乘法模板。需要注意的就是下推和修改时要规定好两种操作的优先级, 一般是区间覆盖大于乘法, 乘法大于加法. 修改和下推时要保持一致. 修改时每次只处理一种操作, 其他的标记先下推.
最近写线段树的时候需要注意, 下推时老是忘了下推标记.
C
权值线段树实现整体 Kth: 区间表示权值落在
实现静态区间 Kth: 考虑前缀和思想, 用 n 棵权值线段树维护
动态区间 Kth: 就是要动态维护前缀和, 那么可以用树状数组的方式来管理 n 棵权值线段树. 这样查询或修改的时候, 左右端点可能涉及到最多
动态开点的线段树空间消耗不小, 如果用指针分配与存储, 64 位指针比 32 位下标整数多消耗一倍空间, 还有分配的开销, 不是最优解. 使用 vector
做内存池不能解决问题, 因为 vector
每次扩张两倍空间, 扩张时复制还要消耗额外空间, 容易超内存导致奇怪的 RE. 动态开点线段树的空间消耗不好估计, 较好的方案是算好其他数组的开销, 剩下的内存都预先分配给内存池 (直接开全局数组或者 vector::reserve
).
D
平衡树模板,写了一个简单的 Treap。
E
可以用 CDQ 分治.
不妨反转操作的顺序, 考虑从排列中不断删点. 对答案有贡献的点对位置下标
转化成三维偏序问题. CDQ 分治的基本思路:
- 递归解决左半区间的点对 (左区间已递归排序)
- 递归解决右半区间的点对 (右区间已递归排序)
- 在左右分别有序的情况下, 讨论跨越左右区间的点对的贡献
- 排序整个区间
右侧对左侧, 左侧对右侧的点的贡献用树状数组维护前缀和统计. 注意每完成一轮统计后, 清空树状数组不应用全部赋值 0 的方式, 这样会超时, 应该只还原修改过的点. 详细的处理方式见代码注释.
I
极端卡常的并查集模板。不做启发式,直接随机合并的并查集显然被卡掉了。按秩合并的正确并查集写法,维护每个集合的大小,每次只把小的集合合并到大的集合中,才能保证复杂度是阿克曼函数。
按秩合并有两种写法,一种是严格维护集合大小,一种是维护合并次数,二者区别不大。
1 | inline void unite(int a, int b) { |
或者
1 | inline void unite(int a, int b) { |
尝试过一行并查集和展开递归为循环的写法,区别不大
1 | inline int find(int u) { |
卡常心得:
- 对于 GCC 7.3.0,
inline
对产生的汇编没有任何影响。 - 展开递归为循环在用时上没有显著区别
- 由于每次只乘2,龟速模对常数影响巨大
龟速模:
1 | while (ans >= MOD) ans -= MOD; |
龟速模的汇编:
1 | .L16: |
而普通模 ans %= MOD
会没有直接的硬件实现,会产生大量指令:
1 | mov rcx, QWORD PTR [rbp-32] |
J
STL 数据结构也叫数据结构
思想就是商品价格从大到小枚举,每个商品贪心匹配能用的最小的纸币,找不到则消耗一次修改次数。最后还有剩余的修改次数,则把已有的匹配中差值最大的改成 0.
匹配纸币的过程利用 multiset
的 lower_bound
实现,匹配到纸币后顺手把差值丢进 priority_queue
方便求最大 k 个。注意如果没有匹配合适的纸币,需要花费修改次数时,不能按照题解说的,随便取一张纸币拿出集合,因为不能确定随便一张纸币以后还会不会用到。但是可以不做出队操作,自然最后剩下的纸币就是要修改的,也不用处理了。
K
线段树套线段树。外层线段树维护列,叶子节点对应一整行的内层线段树,非叶子节点对应行的范围。内层线段树维护每行上区间的信息。
查询时,先处理外层列范围,外层节点需要分割区间时,和普通线段树一样递归查询,不分割区间时,调用节点上的内层线段树查询行范围。内层线段树就是普通的一维线段树查询。
修改时,利用搜索回溯,先更新叶子节点上的行线段树,非叶子节点的内层数更新叶子节点时,利用外层树上节点的孩子更新叶子的值,然后照常上推。
查询和修改操作都是
理论上也有可能写四分树来实现,但树套树更常见,并且更有推广练习的价值。
L
先写个 map
离散化,set
维护区间内出现次数,同时维护次数最大值。很不幸,复杂度不对,常数卡的紧,没法再承受一个
众数问题,增加元素容易,删除元素难,考虑回滚莫队。将区间以左端点分块为第一关键字,右端点为第二关键字排序,暴力回答左右端点同一分块的区间,最多
需要注意的是,暴力回答的查询与莫队过程无关,应该用单独的计数数组统计答案,不能和莫队过程公用。
M
树上莫队模版. 使用莫队算法容易解决一维情况的区间颜色计数问题, 可以通过求树的欧拉序, 将树上的路径转化为一维序列.
例如样例中的树, 求出它的一种欧拉序
1 | 1 4 8 8 4 2 2 3 7 7 6 6 5 5 3 1 |
记进入每个节点时欧拉序中的下标是 enter[u]
, 离开时是 leave[u]
, 不妨设 enter[u] < enter[v]
则发现:
- v 在 u 的子树中, 欧拉序中从
enter[u]
到enter[u]
的区间内, 只出现一次的点对应 u 到 v 的路径 - v 不在 u 的子树中, 即
lca(u, v) != u
时, 欧拉序中leave[u]
到enter[v]
的区间以及lca(u, v)
单点对应 u 到 v 的路径
可以用额外一个数组来处理 "只出现一次" 的条件, 于是利用欧拉序, 树上的路径查询变为一维区间查询, 可用莫队解决. 欧拉序的长度是
LCA 查询可以用很多方法, 倍增, 离线, 树剖, 已经求出欧拉序了还能用 ST 表, 总的来说树剖常数小一点, 快一点.
Q
先考虑解决一维区间上的颜色段计数问题. 可以用线段树维护, 每个区间维护左端和右端的颜色, 以及区间内颜色段的数量. 合并区间答案时, 颜色段数量直接求和, 若左区间右端点和右区间左端点的颜色相同, 则应当合并为同一段, 区间答案减一.
转化到树链剖分上, 注意到此问题的区间合并要求区间具有方向性, 需要小心处理. 树剖的区间合并是可以具有方向性的, 利用每一条重链上对应的线段树区间, 从左到右深度从浅到深. 以此维护合并时区间的方向, 在恰当的时机交换左右端点的颜色, 小心处理树剖查询中交换 x
和 y
的写法, 可以实现保持方向性的树上路径合并.
Z
Splay 模板,维护可分裂合并的序列。Splay 好用的关键在于无论什么操作都要把目标节点 splay 到根节点,才能保证均摊复杂度,不要忘了 splay 了。
另外是 splay 有维护父亲指针的写法和不维护父亲指针的写法, 个人觉得不维护父亲的写法方便一点.

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License
Permalink: https://duanyll.com/2022/05/21/UESTC-ICPC-Training-Data-Structure/