数据结构杂记

· · 算法·理论

线段树单侧递归

  1. 板题：楼房重建

单点修改，查询全局有多少位置是前缀最大值。

sol:

考虑线段树，在每个节点上记 \max，需要解决的问题是合并两个节点。

假设两个节点是 A,B，B 分成 C,D。

如果 A 最大值大于 B 最大值，则找不到。

否则如果 A 最大值大于 C 最大值，递归 D；否则递归 C。

于是每次单侧递归 O(\log n)，总复杂度 O(n\log^2 n)。

  1. Distinct Integers

单点修改，差区间无重子区间个数。

sol:

维护 p_i 表示上一个等于 i 的下标，转化为区间前缀最大值的和。

同例1，只是加了一些贡献。

  1. Hungry Cow P

每天如果有干草就会吃 1 份，没有就不吃。有序列 a，表示第 k 天送 a_k 份干草，初始时 a_k=0。

每次操作单点修改，查询此时有干草吃的日期编号的和。

sol:

维护：区间的答案，有多少天可以吃到，溢出了多少份干草。

仍然假设两个节点是 A,B，B 分成 C,D。

4. **Nastya and CBS** ### 线段树、平衡树 1. **括号修复** 给定括号序列，支持：区间赋值、翻转、逐个翻转，查询区间最少修改次数。 **sol:** 区间答案为前缀最大与后缀最小之和除以 $2$。 平衡树记录区间和、前缀最大小、后缀最大小即可，下传标记十分简单。 ### 颜色段均摊 **特点**：修改有区间染色操作。 使用平衡树维护区间的颜色连续段。区间染色每次最多只会增加 $O(1)$ 个连续颜色段，于是均摊的颜色段插入删除次数 $O(n+m)$。 ### 一类复杂度均摊问题 1. **The Child and Sequence** 单点修改，区间取模，区间和。 **sol:** 取模一次至少除以 $2$，于是维护区间 $\max$ 暴力线段树，复杂度 $O(n\log n)$。 2. **Bear and Bad Powers of 42** 如果一个正整数不是 $42$ 的次幂，则它是好的。 给定序列 $a$，初始所有数都是好的。需要支持：单点查询，区间赋值为一个好的数，区间反复加上 $x$ 直到所有数都变好。 **sol:** 注意到 $42$ 的次幂很少，考虑维护每个数到最近的 $42$ 次幂的距离。 区间赋值操作最多只会增加 $O(1)$ 个相同的数的连续段，因此增加的操作次数为 $\log_{42}qV$。注意，我们是将连续段看成一个数处理，因此若当前区间被打上区间覆盖的懒标记，说明当前区间仅有一种数。 于是复杂度 $O(n\log_{42}(nV)\log n)$。 3. **TEST_69** 区间对一个数取 $\gcd$，区间求和。 **sol:** 一个数 $x$ 对 $y$ 取 $\gcd$ 后还是自己的因数，因此 $x$ 变化的次数不会超过 $O(\log x)$。 由于每个数改动的次数较小，如果 $x=\gcd(x,y)$，则区间不需要进行操作就没必要递归了。因此我们只需要维护区间最小公倍数并判断最小公倍数能否整除该数即可。 ### 倍增值域分块 带 $\log$ 时间复杂度的均摊，常见类型：每个数被操作一次之后可能减小的很少，操作很多次后减半。 一般是 $\ge x$ 的减 $x$ 这种形式的问题适合用倍增值域分块解决。这个套路有一定技巧性，需结合具体问题具体分析。 1. **T-Shirts** 有 $n$ 种 T 恤，每种有价格 $c_i$ 和品质 $q_i$。 有 $m$ 个人要买 T 恤，第 $i$ 个人有 $v_i$ 元，每人每次会买一件买得起的 $q_i$ 最大的 T 恤。若有多个 $q_i$ 最大的，会从价格低的开始买。所有人之间是独立的。问最后每个人买了多少件 T 恤。 **sol:** 从人的角度不好处理，考虑计算衣服对每个人的影响。 把 $q_i$ 从大到小排序。我们维护每个人剩余的钱 $a_i$ 和买的衣服数 $b_i$。对于每件衣服 $i$，相当于全局把 $a_j\ge c_i$ 的减去 $c_i$，并且 $b_i$ 加一。 用一棵平衡树维护每个人的钱数（从小到大）。对于衣服 $i$，考虑把序列分成三块：$[1,c_i),[c_i,2c_i),[2c_i,+\infty)$。显然，第一部分不会被操作，第三部分被操作后相对位置没有变化，打标记即可，因此我们只需暴力修改第二部分。 可以发现，$[c_i,2c_i)$ 中的数至少减半了，于是每个数最多暴力操作 $\log$ 次，复杂度 $O((n+m)\log n\log v)$。 ### 可持久化数据结构 1. **异或运算** 给定两个数组 $a,b$，定义一个 $n\times m$ 的矩形，对于 $(i,j)$ 这个格子的权值为 $a_i\oplus b_j$。$p$ 次查询一个子矩形内第 $k$ 大的数。 $1\le n\le 10^3,1\le m\le 3\times 10^5,1\le p\le 500$。 **sol:** 考虑只有一行，维护一个区间异或 $x$ 的第 $k$ 大值。 使用可持久化字典树（类似主席树），对于 $x$ 的每一位考虑。这一位是 $1$ 相当于交换了左右子树（无需真的交换，只是意义上），比较当前 $k$ 与左子树的大小，来决定向左、向右递归。 发现 $n$ 很小，于是对于每一行分别考虑异或 $a_i$，一共 $n$ 棵树一起递归即可。 2. **度度熊玩数组** 给一个数组，每次删除一个数，查询不包含删除数的区间的权值和和 $k$ 的最小差值。 **sol:** 正难则反，考虑插入每个数的贡献。插入一个数会合并两个相邻区间。使用启发式合并的方法，需要讨论小的部分是前一段还是后一段。 如果小的是前一段，那么对于前一段的每一个后缀 $s_x$，求出后一段最大的前缀 $p_y$，满足 $s_x+p_y\le k$，也就是 $p_y\le k-s_x$。 考虑求出原序列的前缀和 $h$，条件变为 $h_y\le$ 某常数，简单解决。 3. **middle** **sol:** 题意可以转化为必须选出 $[b,c]$ 这个区间，两边可以各增加一个 $[l,b)$ 和 $(c,r]$，其中 $l$ 在 $[a,b]$ 中，$r$ 在 $[c,d]$ 中。 求中位数通常使用二分。二分 $x$，把小于 $x$ 的设为 $-1$，大于等于 $x$ 的设为 $1$。如果区间和 $\ge 0$，则 $\ge x$ 的数出现次数 $\ge$ 区间长度的一半，则中位数 $\ge x$。 一个数 $a_i$ 的贡献只会在 $x$ 从比 $a_i$ 大变成比 $a_i$ 小的时候改变。那么我们每次把 $x$ 增大，只会对 $a_i=x$ 的位置造成影响，这样每个数的贡献都只会改变 $1$ 次。 于是可以使用主席树，把所有可能的 $x$ 的情况建主席树。查询时查一个区间的前缀最大与后缀最大即可，可以简单维护。 ### 莫队 1. **大数** 给数字串 $S$ 和数 $p$，每次查询 $S$ 的一个子串中有多少子串是 $p$ 的倍数。 **sol:** 计算串 $S$ 的后缀 $h$，考虑把一个字串表示为后缀相减的形式。 对于区间 $[l,r]$，假设它表示的数是 $a_1\cdots a_n$，那么 $h_l-h_{r+1}$ 可以表示为 $a_1\cdots a_n00\cdots 0$。 此时如果 $\gcd(p,10)=1$，那么可以直接把后缀模 $p$，转化为区间相等数的个数，莫队解决。 否则 $p=2,5$，那么只需考虑末位，直接做即可。 2. **美好的每一天** 给一个字符串，每次查询每个区间中有多少个子区间满足重排之后可以成为一个回文串。 **sol:** 回文串只可能是所有字母都是偶数个或者仅有一个字母是奇数个，于是可以使用异或判定。 我们把每个字母表示为 $2$ 的不同次幂，于是一个区间重排可以成为回文串说明区间异或值为 $0$ 或 $2^k$。 计算出前缀异或数组，问题变为区间中选出两个数使得异或和为 $2^k$，莫队计算即可。 ### 根号分治 **经典问题：** 给序列 $a$，每次给出 $x,y$，求 $a_i=x,a_j=y$ 的 $|i-j|$ 最小值。 **sol:** 按出现次数根号分治。 $x,y$ 都小：归并排序，线性，每次 $O(\sqrt n)$。 否则预处理每个大的颜色与每个位置的最小距离，直接计算。 总复杂度 $O(n\sqrt n)$。 1. **Regions** 2. **作业** 维护一个集合，每次加入一个元素或者询问所有元素 $\bmod Y$ 最小的值。 **sol:** 根号分治，如果模数不超过 $\sqrt V$，那么预处理即可。 否则，枚举模数的倍数，二分找到集合中第一个大于它的数，计算差值即可。 3. **ODW** 给定一棵树，每条边长度都为 $1$，点有点权。 多次询问，每次给出一个 $1$ 到 $n$ 的全排列 $b$，第 $i$ 次从 $b_i$ 点走到 $b_{i+1}$ 点，每步往前走 $c_i$ 长度。询问经过的所有点的权值和。 **sol:** 仍然根号分治，让 $c\ge\sqrt n$ 的暴力跳。 对于 $c\le\sqrt n$ 的，预处理 $f_{i,j}$ 表示从 $i$，每次跳 $j$ 步，跳到根节点的权值和。查询就类似树上差分即可。 那么这样暴力跳的复杂度是 $O(n\sqrt n\log n)$，预处理是 $O(n\sqrt n)$。 对时间进行优化，可以使用长链剖分，每次 $O(1)$ 查询 $k$ 级祖先，总复杂度可以做到 $O(n\log n+n\sqrt n)$。 ### 分块 1. **弹飞绵羊** 一条直线上摆 $n$ 个装置，每个装置设定初始弹力系数 $k_i$，当到达第 $i$ 个装置时，会往后弹至第 $i+k_i$ 个装置，若不存在第 $i+k_i$ 个装置，则被弹飞。 单点修改，查询从第 $i$ 个装置起步时，被弹几次后会被弹飞。 **sol:** 考虑把序列分成 $\sqrt n$ 个块。在块内，我们维护每个元素弹出块到达的位置，以及多少步会弹出块。 对于修改操作，直接暴力重构块即可，复杂度 $O(\sqrt n)$。 对于查询操作，使用维护的数组在块间跳，复杂度也是 $O(\sqrt n)$。 于是总复杂度 $O(n\sqrt n)$。 ### 树上问题 1. **情报传递** 给你一棵树，初始每个位置没有点权。每次标记一个点，查询一条链中有多少点的点权大于 $c$。 对于一个被标记的点，每天点权都固定加 $1$。 **sol:** 这个每天点权加 $1$ 不好处理，考虑第二种操作。显然，一个点的点权大于 $c$，相当于当前时间减标记时间大于 $c$，即当前时间减 $c$ 大于标记时间。 这里可以使用主席树在线 $O(n\log^3 n)$。还可以离线，把询问按当前时间减 $c$ 的值排序。按时刻从小到大处理，标记相当于把一个点权值变为 $1$，查询相当于链上求和。树上差分+树状数组即可做到 $O(n\log n)$。 2. **TEST_68** 给一棵树，点 $i$ 有点权 $a_i$。 对每个点 $x$，求出它所在子树外的所有点中，选两个点点权异或的最大值。 **sol:** 考虑使用 trie 找到一组 $(x,y)$ 满足 $a_x\oplus a_y$ 最大。我们发现，除了 $x$ 到根和 $y$ 到根的路径以外，其他点的子数补中都包含 $x,y$，所以它们的答案均为 $a_x\oplus a_y$。 对于这两条路径，我们从根向下 dfs。每次从一个点 $x$ 挪到它的儿子时，子树的补只增不减，于是使用 trie，每次插入一些节点，动态维护异或最大值即可。 ### 树链剖分 1. **大融合** 给定 $n$ 个点，支持每次加入一条边或查询经过一条边的路径数量。 **sol:** 容易发现，对于一条边 $(x,y)$，当前根节点为 $r$，那么经过这条边的路径数为 $s_x(s_r-s_x)$。 于是使用并查集维护根节点，每次加 $(x,y)$（$y$ 是 $x$ 祖先）时，把 $y$ 到 $r$ 的路径加上 $s_x$，查询时使用上面的公式计算。 可以使用树上差分，每次 $y$ 处加 $s_x$，$r$ 的父亲处减 $s_x$。计算 $s$ 时求子树和。树状数组+dfs 序即可。 2. **Tavas on the Path** 给定一棵树，边有边权。 有 $m$ 个询问：求 $u$ 到 $v$ 的路径，假设第 $i$ 条边权为 $x_i$，构造一个长度为 $p$ 的 $01$ 串 $s$，如果 $x_i\ge l$，那么 $s_i=1$，否则 $s_i=0$。 对于串 $s$，假设第 $i$ 段连续 $1$ 的长度为 $pi$，那么输出所有 $f_{p_i}$ 的和，其中 $f$ 数组一开始就给出。 **sol:** 离线询问，把 $l$ 排序。扫一遍，每次相当于把一个点的点权变为 $0$。 使用线段树维护区间连续段，单点修改，查树上路径，树链剖分即可。 ### 扫描线 1. **窗口的星星** 给定一个窗子的大小 $H\times W$，再给定每个星星的位置 $(x,y)$ 和亮度 $l$，求出最多能有总和多亮的星星出现在窗口上。 **sol:** 我们对于每一个星星，考虑它的影响：显然，一颗星星 $(x,y)$ 被窗口包含当且仅当窗口左下角在 $(x-H,y-W)\sim (x,y)$ 这个矩形范围中。 于是枚举星星，把它影响范围中的每一个点加上 $l$，最后查全局最大值即可。 #### 区间子区间问题 给一个序列，每次查询区间有多少子区间满足某个条件。 将每个区间看做二维平面上的点，区间的子区间转换为查询一个 2-side 矩形内有多少点满足某条件。 我们现在只处理一个矩形，假设左上角为 $(x,y)$。扫描线扫 $x$ 轴，扫到一个位置有一棵线段树。这个矩形的答案就是 $x\sim r$ 位置的所有线段树的 $1\sim y$ 区间求和，也就是求线段树历史版本和。线段树上维护一些标记即可。 2. **序列** 给你一个序列，每次查询区间所有子区间的最小值的和。 **sol:** 板题，难点在于维护线段树。 $\ \ $ 3*.**Pudding Monsters** 下一题的前置知识。 给定一个 $n\times n$ 的棋盘，其中有 $n$ 个棋子，每行每列恰好有一个棋子。 求共有多少个 $k\times k$ 的子棋盘中恰好有 $k$ 个棋子（对于所有 $k$ 统计和）。 **sol:** 因为每行每列只有一个，于是把棋盘投影到序列上，$a_x=y$ 等价于在 $(x,y)$ 处有一个值。 问题转化为有多少 $(l,r)$ 满足 $[l,r]$ 中的 $\max-\min=r-l$，也就是维护 $\max-\min+l-r=0$ 的数量。 发现 $=0$ 的数量不好维护，但我们发现，由于原串是一个排列，所以 $\max−\min+l-r\ge 0$。于是维护最小值和最小值的数量即可。 对 $r$ 扫描线，考虑 $r$ 想要挪一位对当前线段树的影响。首先，显然需要全局减一。对于最大值的改变，我们维护单调递减栈 $s$，如果栈顶 $t$ 小于当前数，那么线段树上 $s_{t-1}+1$ 至 $s_t$ 位置都会改为当前数。 可以这样理解：线段树上的节点 $[L,R]$ 表示原序列中 $[L,r],[L+1,r],...,[R,r]$ 这些区间的答案。那么区间 $[s_{t-1+1},r]$ 到 $[s_t,r]$ 的最大值都会改为当前数。 最小值处理同理，于是做完了。 3. **Good Subsegments** 同上一题，只不过询问区间中满足条件的子区间个数。 **sol:** 套区间子区间问题板子。相当于矩阵加减，矩阵求 $0$ 的个数。 同样线段树历史版本和即可。 4. **Beautiful Subsequences** 给排列 $a$，求 $\max-\min+l-r\le k$ 的区间 $[l,r]$ 个数。 **sol:** 考虑到 $\max-\min+l-r\ge 0$，所以只有当这个值为 $0\sim k$ 时才满足条件，这只有 $4$ 个值。 考虑扫描线，线段树维护区间前 $4$ 小值和出现次数即可。