2022 UESTC ICPC Training for Data Structures

A

首先对于每个物品，连续整除 d，匹配到能打开的最小钥匙。在钥匙编号从大到小排序后，可以 完成这一过程。容易理解，要使不同的钥匙使用量最小，只需要贪心地使用能打开的最小钥匙。

接下来问题转化为区间不同颜色数查询。由于 很小, 不需要使用莫队算法, 可以通过 ST 表高效解决. 通过状压的方式, 维护区间内需要的钥匙的集合 (自然地, 不存在钥匙的物品可将集合表示为空集), 这样可以用按位或合并重叠区间的答案. 输出答案时, 对状压集合进行 popcount 操作即可.

需要注意的是, __builtin_popcount 仅接受 32 位的输入, 使用 64 位整形时应使用 __builtin_popcountll.

B

线段树区间加法、区间乘法模板。需要注意的就是下推和修改时要规定好两种操作的优先级, 一般是区间覆盖大于乘法, 乘法大于加法. 修改和下推时要保持一致. 修改时每次只处理一种操作, 其他的标记先下推.

最近写线段树的时候需要注意, 下推时老是忘了下推标记.

C

权值线段树实现整体 Kth: 区间表示权值落在 范围内的元素数量, 然后二分查询. 具体来说, 先判断 左儿子区间元素数量, 与 k 比较, 决定下一步查询左儿子还是右儿子. (很类似平衡树的 Kth 查询过程). 修改时, 照常维护区间和就行.

实现静态区间 Kth: 考虑前缀和思想, 用 n 棵权值线段树维护 坐标区间, 查询时通过前缀和的方式, 统计区间和时需要把右端点的和减去左端点的和, 然后再决定查权值线段树上的左儿子还是右儿子. 直接开 n 棵静态线段树肯定开不下, 于是用主席树 (动态开点, 节约空间).

动态区间 Kth: 就是要动态维护前缀和, 那么可以用树状数组的方式来管理 n 棵权值线段树. 这样查询或修改的时候, 左右端点可能涉及到最多 棵权值线段树的和, 都需要进行处理.

动态开点的线段树空间消耗不小, 如果用指针分配与存储, 64 位指针比 32 位下标整数多消耗一倍空间, 还有分配的开销, 不是最优解. 使用 vector 做内存池不能解决问题, 因为 vector 每次扩张两倍空间, 扩张时复制还要消耗额外空间, 容易超内存导致奇怪的 RE. 动态开点线段树的空间消耗不好估计, 较好的方案是算好其他数组的开销, 剩下的内存都预先分配给内存池 (直接开全局数组或者 vector::reserve).

D

平衡树模板，写了一个简单的 Treap。

E

可以用 CDQ 分治.

不妨反转操作的顺序, 考虑从排列中不断删点. 对答案有贡献的点对位置下标 , 除了逆序对的基本条件 且 以外, 还要满足删除时间的条件 (记 为 被删除的时刻):

转化成三维偏序问题. CDQ 分治的基本思路:

1. 递归解决左半区间的点对 (左区间已递归排序)
2. 递归解决右半区间的点对 (右区间已递归排序)
3. 在左右分别有序的情况下, 讨论跨越左右区间的点对的贡献
4. 排序整个区间

右侧对左侧, 左侧对右侧的点的贡献用树状数组维护前缀和统计. 注意每完成一轮统计后, 清空树状数组不应用全部赋值 0 的方式, 这样会超时, 应该只还原修改过的点. 详细的处理方式见代码注释.

I

极端卡常的并查集模板。不做启发式，直接随机合并的并查集显然被卡掉了。按秩合并的正确并查集写法，维护每个集合的大小，每次只把小的集合合并到大的集合中，才能保证复杂度是阿克曼函数。

按秩合并有两种写法，一种是严格维护集合大小，一种是维护合并次数，二者区别不大。

inline void unite(int a, int b) {
    int af = find(fa[a]);
    int bf = find(fa[b]);
    if (af == bf) return;
    if (rk[af] < rk[bf]) {
        fa[af] = bf;
    } else {
        fa[bf] = fa[af];
        if (rk[af] == rk[bf]) rk[af]++;
    }
}

或者

inline void unite(int a, int b) {
    int af = find(fa[a]);
    int bf = find(fa[b]);
    if (af == bf) return;
    if (cc[af] > cc[bf]) {
        fa[bf] = af;
        cc[af] += cc[bf];
    } else {
        fa[af] = bf;
        cc[bf] += cc[af];
    }
}

尝试过一行并查集和展开递归为循环的写法，区别不大

inline int find(int u) {
    while (u != fa[u]) {
        fa[u] = fa[fa[u]];
        u = fa[u];
    }
    return u;
}

卡常心得：

1. 对于 GCC 7.3.0, inline 对产生的汇编没有任何影响。
2. 展开递归为循环在用时上没有显著区别
3. 由于每次只乘2，龟速模对常数影响巨大

龟速模：

while (ans >= MOD) ans -= MOD;

龟速模的汇编：

.L16:
        cmp     QWORD PTR [rbp-32], 1000000006
        jle     .L15
        sub     QWORD PTR [rbp-32], 1000000007
        jmp     .L16
.L15:

而普通模 ans %= MOD 会没有直接的硬件实现，会产生大量指令：

mov     rcx, QWORD PTR [rbp-32]
movabs  rdx, -8543223828751151131
mov     rax, rcx
imul    rdx
lea     rax, [rdx+rcx]
sar     rax, 29
mov     rdx, rax
mov     rax, rcx
sar     rax, 63
sub     rdx, rax
mov     rax, rdx
imul    rax, rax, 1000000007
sub     rcx, rax
mov     rax, rcx
mov     QWORD PTR [rbp-32], rax

J

STL 数据结构也叫数据结构

思想就是商品价格从大到小枚举，每个商品贪心匹配能用的最小的纸币，找不到则消耗一次修改次数。最后还有剩余的修改次数，则把已有的匹配中差值最大的改成 0.

匹配纸币的过程利用 multiset 的 lower_bound 实现，匹配到纸币后顺手把差值丢进 priority_queue 方便求最大 k 个。注意如果没有匹配合适的纸币，需要花费修改次数时，不能按照题解说的，随便取一张纸币拿出集合，因为不能确定随便一张纸币以后还会不会用到。但是可以不做出队操作，自然最后剩下的纸币就是要修改的，也不用处理了。

K

线段树套线段树。外层线段树维护列，叶子节点对应一整行的内层线段树，非叶子节点对应行的范围。内层线段树维护每行上区间的信息。

查询时，先处理外层列范围，外层节点需要分割区间时，和普通线段树一样递归查询，不分割区间时，调用节点上的内层线段树查询行范围。内层线段树就是普通的一维线段树查询。

修改时，利用搜索回溯，先更新叶子节点上的行线段树，非叶子节点的内层数更新叶子节点时，利用外层树上节点的孩子更新叶子的值，然后照常上推。

查询和修改操作都是 的复杂度。

理论上也有可能写四分树来实现，但树套树更常见，并且更有推广练习的价值。

L

先写个 的普通莫队，用 map 离散化，set 维护区间内出现次数，同时维护次数最大值。很不幸，复杂度不对，常数卡的紧，没法再承受一个 了。

众数问题，增加元素容易，删除元素难，考虑回滚莫队。将区间以左端点分块为第一关键字，右端点为第二关键字排序，暴力回答左右端点同一分块的区间，最多；左端点同一分块的区间中的处理中，可以保证右端点单调增加，而左端点的处理，可以缓存住左端点位于分块右边界侧的答案，每次查询都重新从分块右边界向左推进边界，记录当前查询，然后将左端点和答案重置到缓存的分块右边界上，左端点推进次，右端点无需删除，不影响总复杂度。

需要注意的是，暴力回答的查询与莫队过程无关，应该用单独的计数数组统计答案，不能和莫队过程公用。

M

树上莫队模版. 使用莫队算法容易解决一维情况的区间颜色计数问题, 可以通过求树的欧拉序, 将树上的路径转化为一维序列.

例如样例中的树, 求出它的一种欧拉序

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 有维护父亲指针的写法和不维护父亲指针的写法, 个人觉得不维护父亲的写法方便一点.