数据结构练习 1
线段树合并/分裂
习题一
题意
给定由 $1\sim n$ 的排列构成的序列 $A$，要求支持以下下两种操作：
- 将 $A_{l\sim r}$ 按升序排列
- 将 $A_{l\sim r}$ 按降序排列
$m$ 次操作后询问位置 $p$ 上的数值。
题解
考虑初始时构造 $n$ 棵权值线段树，每个线段树维护区间 $[i,i](1\le i\le n)$。
每次排序操作将所有代表区间含于 $[l,r]$ 的线段树合并，发现合并完成的同时也完成了排序。
但由于区间 $[l,b]$ 可能已经属于某个区间 $[a,b]$，所以需要线段树分裂将其分裂为 $[a,l-1],[l,b]$。
同样也需要将区间 $[c,d]$ 分裂为 $[c,r],[r+1,d]$。
最后将 $[l,b]\cdots [c,r]$ 等区间合并即可，注意打标记维护区间的升序/降序情况。
初始化时间复杂度 $O(n\log n)$，产生点数 $O(n\log n)$。每次分裂时间复杂度 $O(\log n)$，且增加 $O(\log n)$ 个点。
每次合并操作时间复杂度等于合并的点数，于是一定不会超过初始化和分裂生成的总点数。
对于查询操作，考虑单独将区间 $[p,p]$ 分裂出来然后 $\text{dfs}$ 沿唯一路径到达叶子结点即可，时间复杂度 $O(\log n)$。
考虑 ODT 维护区间，总时空间复杂度 $O((n+m)\log n)$。
习题二
题意
给定一棵以 $1$ 为根的有根树，每个点有一个权值，且度数不超过 $2$。
若 $i$ 为叶子结点，则 $i$ 的权值等于 $v$，否则它的权值有 $p$ 的概率为儿子结点中的较大值，$1-p$ 的概率为儿子节点中的较小值。
假设 $1$ 号节点有 $m$ 中可能取值，$V_i$ 为所有可能值中第 $i$ 小的取值，$D_i$ 为取到第 $i$ 小的取值的概率，询问
$$\sum_{i=1}^m iV_iD_i^2$$
数据保证所有叶子节点权值互异。
题解
先对所有权值进行离散化，设 $D(i,j)$ 表示节点 $i$ 取值为 $j$ 的概率。
对树进行 $\text{dfs}$，如果该节点是叶子节点，直接可知该结点 $D$ 数组在该点权值处为 $1$，其余处为 $0$。
如果该节点只有一个子节点，则该节点可以直接继承子节点的 $D$ 数组。
如果该节点有两个子节点，对取值 $i$，由于叶子节点取值互异，不难得到状态转移：
$$D(u,i)=\left(D(l,i)\left(p_i\sum_{j=1}^{i-1}D(r,j)+(1-p_i)\sum_{j=i+1}^mD(r,j)\right)+D(r,i)\left(p_i\sum_{j=1}^{i-1}D(l,j)+(1-p_i)\sum_{j=i+1}^mD(l,j)\right)\right)$$
考虑用权值线段树维护每个节点的 $D$ 数组。对于叶子节点和只有一个子节点的节点，不难维护。
对于有两个子节点的节点和某个确定的取值 $i$，显然至多只有一个子节点满足该节点取值为 $i$ 的概率不为 $0$。
于是不可能出现被合并的两棵线段树拥有重复的叶子节点的情况。于是合并的终止条件一定某个线段树该节点为空。
不妨设左节点的线段树非空，且当前线段树节点代表区间为 $[x,y]$，于是对 $i\in [x,y]$ 有
$$D(u,i)=D(l,i)\left(p_i\sum_{j=1}^{x-1}D(r,j)+(1-p_i)\sum_{j=y+1}^mD(r,j)\right)$$
考虑线段树合并过程中维护两棵线段树的区间前缀和 $[1,x-1]$ 和后缀和 $[y+1,m]$ 即可。
最后对 $1$ 节点的线段树 $\text{dfs}$ 即可得到答案。时空间复杂度 $O(n\log n)$。
可持久化数据结构
习题一
题意
给定一棵点权树，每次询问某条路径上第 $k$ 小的权值，强制在线。
题解
类比区间第 $k$ 小查询，考虑差分，对每个结点建权值线段树维护该结点到根节点之间的所有结点的权值集合。
对于路径询问操作跑 $u+v-\text{LCA}(u,v)-\text{fa}(\text{LCA}(u,v))$ 构成的线段树即可。
习题二
题意
给定一个长度为 $n$ 的序列。每次询问给定两个区间 $[l_1,r_1]$ 和 $[l_2,r_2]$，询问所有满足 $l\in [l_1,r_1],r\in [l_2,r_2]$ 的区间 $[l,r]$ 的中位数的最大值。
其中序列下标从 $0$ 开始，中位数定义为所选区间中第 $\lfloor \frac {r-l+1}2\rfloor$ 小的数，强制在线。(数据保证 $l_1\lt r_1\lt l_2\lt r_2$)
题解
考虑二分答案，对每个答案 $x$，将小于 $x$ 的数设为 $-1$，其他的数设为 $1$，于是 $x$ 可以满足条件当且仅当所选区间满足区间和不小于 $0$。
首先 $[r_1+1,l_2-1]$ 必选，然后考虑取 $[l_1,r_1]$ 的最大后缀和 $[l_2,r_2]$ 的最大前缀即可，这可以用线段树维护。
考虑答案 $x$ 和 $x+1$ 的线段树大部分相同，考虑可持久化线段树维护所有可能答案，答案 $x+1$ 的线段树只需要在答案 $x$ 的线段树上修改即可。
将数据值域离散化即可，时间复杂度 $O(n\log n+q\log^2 n)$，空间复杂度 $O(n\log n)$。
习题三
题意
给定一个长度为 $n$ 的字符串 $S$ 和 $m$ 个询问。每次询问所有 $S[a,b]$ 的子串和 $S[c,d]$ 的 $\text{LCP}$ 的最大值。
题解
发现所有 $S[a,b]$ 的子串和 $S[c,d]$ 的 $\text{LCP}$ 的最大值等价于所有 $S[a,b]$ 的后缀和 $S[c,d]$ 的 $\text{LCP}$ 的最大值。
考虑二分答案，对每个答案 $x$，只需要存在 $p$ 满足 $\text{LCP}(S[p,b],S[c,d])\ge x$ 即可。
而要满足上式必有 $\min(b-p+1,d-c+1)\ge x$，于是上式等价于 $\text{LCP}(S[p,n],S[c,n])\ge x,p\le b-x+1$。
考虑建立后缀数组，于是满足 $\text{LCP}(S[p,n],S[c,n])\ge x$ 的 $p$ 必然是 $sa$ 数组中的一段连续区间，可以通过二分得到该连续区间。
然后对 $sa$ 数组建立主席树查询该连续区间是否存在点属于 $[a,b-x+1]$ 即可。
时间复杂度 $O(n\log n+q\log^2 n)$，空间复杂度 $O(n\log n)$。
习题四
题意
给定一棵以 $1$ 为根的树，接下来 $q$ 次询问。每次询问给定 $a,k$，有多少个二元组 $(b,c)$ 满足：
- 结点 $a,b,c$ 互异
- 结点 $a$ 和结点 $b$ 是结点 $c$ 的祖先
- 结点 $a$ 和结点 $b$ 的距离不超过 $k$
题解
对每次查询操作，答案分为 $b$ 为 $a$ 祖先和 $a$ 为 $b$ 祖先两种。对于 $b$ 为 $a$ 祖先的情况，易知答案为 $(\text{sz}_a-1)\min(d_a-1,k)$。
对于 $a$ 为 $b$ 祖先的情况，易知每个 $a$ 的子树中距离 $a$ 不超过 $k$ 的结点的贡献为该结点的子树大小减一。
于是考虑将每个结点的权值设为该结点的子树大小减一，于是贡献和为所有深度为 $[d_a+1,d_a+k]$ 且 $\text{dfs}$ 序属于 $a$ 的子树的结点的权值和。
于是问题转化为二维偏序问题，考虑主席树统计答案。时间复杂度 $O((n+q)\log n)$。
习题五
题意
给定长度为 $n$ 的序列 $a$ 和 $q$ 个询问。每次询问给定 $b,x,l,r$，输出 $\max_{l\le i\le r}(b\oplus(a_i+x))$。
题解
考虑按高位到低位贪心枚举。假设当前枚举到第 $4$ 为，答案 $\text{ans}=c_1c_2c_3???,b=b_1b_2b_3b_4??$。
优先考虑是否可以使 $\text{ans}=c_1c_2c_31??$，如果 $b_4=1$，则 $\text{ans}\oplus b\in[d_1d_2d_3000,d_1d_2d_3011]$。
如果 $b_4=0$，则 $\text{ans}\oplus b\in[d_1d_2d_3100,d_1d_2d_3111]$。而 $a=\text{ans}\oplus b-x$，于是主席树查询即可。
