【做题记录】数据结构

· · 个人记录

二分答案，设为 mid，把小于 mid 的数设为 0，大于等于 mid 的数设为 1。

然后就很好排序了，查询 [l,r] 中 1 的个数（即区间和），升序则把 0 填区间左边，1 填右边，降序则相反。

最后如果 q 位置的数为 1，说明答案至少为 mid。

因数个数 = 各质因子次数 +1 之积。

小于 \sqrt[3]{x} 的质因子直接用前缀和搞掉。大于 \sqrt[3]{x} 的质因子最多有两个，这些用 Miller-rabin + 二分处理出来，再离散化（并不需要 PR）。然后上莫队即可。

分块。设块长为 T。对每个块维护一个排好序的数组 b。

修改时，整块直接打上标记。对于散块，直接加再排序并不优秀。在原数组中修改后，将 b 按是否要修改分成两队，发现它们各自仍是有序的。二路归并即可。

查询时，二分答案，查询小于答案的数的个数。对于整块，在 b 中二分。对于左右两个散块，暴力统计并不优秀。在 b 中把两个散块要查询的部分取出，再归并起来，就可以二分了。

时间复杂度 O(q\dfrac{n}{T}\log^2n+qT)，T=\sqrt{n}\log n 时最优，为 O(q\sqrt{n}\log n)。

二分答案。设为 mid。把小于 mid 的数设为 -1，大于等于

如果一段区间的和 $\ge 0$，说明其中位数至少为 $mid$。 要判断是否存在一个子区间满足这个条件，考虑让区间和最大，即 $[b+1,c-1]$ 的和 $+\;[a,b]$ 的最大右子段和 $+\;[c,d]$ 的最大左子段和。 用主席树即可。 + [P4688 [Ynoi2016] 掉进兔子洞](https://www.luogu.com.cn/problem/P4688) 首先离散化，注意不要去重。 对于每个区间，用莫队维护 `bitset` 表示数的出现情况。考虑将多个相同的数分开，如果一个数 $x$，出现了第 $b[x]$ 次，给它一个标号 $x+b[x]-1$，删除同理。这样就可以把相同的数字集中在值域上以 $x$ 为左端点的区间内。由于离散化时没有去重，不同数字间互不干扰。最后用三个区间的总长，减去它们对应的 `bitset` 按位与的结果中 $1$ 的个数 $\times 3$ 即可。 小技巧：把询问分成 $10$ 组，防止 MLE。 + [P4689 [Ynoi2016] 这是我自己的发明](https://www.luogu.com.cn/problem/P4689) 先考虑序列上的做法。设 $f(x,y)$ 表示 $[1,x]$ 和 $[1,y]$ 的答案。那么 $[l,r]$ 的答案可表示成 $f(r,r)-f(l-1,r)-f(l,r-1)+f(l-1,l-1)$。然后就可以莫队 / 分块了。 现在到了树上，还有换根，无非就是多了 dfs 序、分类讨论和倍增。 + [P5355 [Ynoi2017] 由乃的玉米田](https://www.luogu.com.cn/problem/P5355) 还是用 `bitset`。维护正反两个 `bitset`，表示每个数的出现情况（对于 $x$，把它放在 `b1` 的 $x$ 处和 `b2` 的 $M-x$ 处，$M$ 表示值域）。 加法：若 $a+b=x$，则 $a=x-b=x-(M-b^\prime)=b^\prime-(M-x)$，即 `b1&(b2>>(M-x))`。 减法：`b1&(b1>>x)` 乘法：暴力枚举因数 除法：若 $x>\sqrt M$，枚举 $a$，检查 $a$ 和 $ax$ 是否都存在；否则，预处理出 $pos_{i,k}$，表示 $[1,i]$ 内最大的 $j$，满足 $a_j\times k=a_i$ 或 $a_i\times k=a_j$，并对每个 $k$ 做前缀最大值。查询时判断 $pos_{r,x}$ 是否 $\ge l$。 + [P6018 [Ynoi2010] Fusion tree](https://www.luogu.com.cn/problem/P6018) 发现 1 和3 操作可以分为父亲和儿子，而父亲很好处理。 对于每个节点，将其所有儿子的权值放到一个 trie 里，并从低位开始（因为要支持加 $1$）。再维护每位上有几个 $1$和一个加法标记。 考虑二进制加法：找到最右边的 $0$，把它右边的 $1$全部变成 $0$，并把这个 $0$ 变成 $1$。对应到 trie 树上就是：交换两个儿子，并往现在的 $0$ 子树走（过去的 $1$ 子树）。 单点修改其实就是在父亲的 trie 中删除再插入。 + [P5385 [Cnoi2019]须臾幻境](https://www.luogu.com.cn/problem/P5385) 用 LCT 维护链上最小值（以边的编号为权值），即最大生成树。 加入边 $i$ 时，若两点已联通，设两点路径上的最小编号为 $p_i$。对于一次询问，考虑一种使编号小的边尽可能被使用，并构成森林的策略选边。如果 $p_i\ge l$，由于 $p_i$ 是路径上的最小编号，路径上的所有边都会出现，边 $i$ 也就没用了。反之，就要把 $i$ 加入森林。所以询问其实是求 $[l,r]$ 中 $p_i<l$ 的数量，用主席树维护。答案就是点数 $-$ 边数。 + [P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III](https://www.luogu.com.cn/problem/P5048) 朴素做法：对每个数开一个 vector，按顺序存储值为这个数的下标。预处理出 $l..r$ 块的答案，枚举散块的每个数，二分出出现次数并和整块的答案比较。 但复杂度是 $O(n\sqrt{q\log n})$，不够优秀。 记录一个 $t_i$ 表示 $i$ 在 $a_i$ 的 vector 中的位置。 枚举散块每个位置 $i$，设当前答案为 $ans$，若 $a_i$ 的 vector 中第 $t_i+ans$ 个数仍不超过 $r$，说明 $a_i$ 更优。然后一直加 $ans$ 直到 vector 中第 $t_i+ans$ 个数超过 $r$ 或不存在。 复杂度证明：设整块答案为 $ans$，那么实际答案一定不超过 $ans+2T$，也就是 $ans$ 最多加 $2T$ 次。 + [P3793 由乃救爷爷](https://www.luogu.com.cn/problem/P3793) 分块 + ST 表。 设块长为 $T$，记录每块最大值，块内的前、后缀最大值，并对整块构建 ST 表。 若区间横跨多个块 $T$，可以 $O(1)$ 求得答案。否则可以暴力，由于数据随机，这些区间的概率为 $\dfrac{T}{n}$。 时间复杂度 $O(q+\dfrac{qT^2}{n}+\dfrac{n}{T}\log n)$，取 $T=\log n$ 最优，为 $O(n+q)$。 + [P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II](https://www.luogu.com.cn/problem/P5047) 莫队二次离线，用值域分块平衡最后查询的复杂度。 + [CF464E The Classic Problem](https://www.luogu.com.cn/problem/CF464E) 堆优 Dijkstra + 主席树 二进制下，加上 $2^k$，其实就是从第 $k$ 位往高位找到第一个 $0$，把它改为 $1$，并把这个 $0$ 到 $k$ 的所有 $1$ 改成 $0$。 只有两次修改，可以上主席树。 比较大小可以用哈希，先判断高位子树是否相等，相等则往低位子树走，否则往高位子树走。 + [P5305 [GXOI/GZOI2019]旧词](https://www.luogu.com.cn/problem/P5305) 有一个 [弱化版](https://www.luogu.com.cn/problem/P4211) 考虑在树上把 $dep^k$ 做差分，即 $v_u=dep_u^k-(dep_u-1)^k$。 对于 $x,y$，把 $1$ 到 $y$ 路径上所有点的点权设为该点的 $v$，其他点点权为 $0$。令 $z=LCA(x,y)$，那么 $1$ 到 $x$ 路径上的点权和就是 $1$ 到 $z$ 的点权和，即 $dep_z^k$。 把询问按 $x$ 排序，就变成了路径修改、路径求和的问题，即： 维护一个数组 $b$，初始为 $0

  1. 对 1 到 x 上的所有点 i，b_i\leftarrow b_i+v_i

  2. 求路径上 b_i 的和。

树剖 + 线段树实现。

对于非叶子节点，设左右子树和整棵子树选到 x 的概率分别是 L_x,R_x,F_x。

F_x=p(L_x\sum\limits_{i<x}R_i+R_x\sum\limits_{i<x}L_i)+(1-p)(L_x\sum\limits_{i>x}R_i+R_x\sum\limits_{i>x}L_i)

用线段树合并优化，递归时维护两个标记表示两棵树分别要乘多少。

分块。区间第 k 小考虑值域分块。

对于每个块，用并查集把值相同的下标合并（从大的下标指向小的下标），并记录每个数的根。这样我们只需要保证根是真正的值。整块修改时判断是否已经有了 y，如果有了就把 x 和 y 合并起来，并把根的值改为 y。散块暴力重构。

设区间长度为 L，对于一个数 x，如果它出现了 k 次，贡献为 x\times 包含 x 的子序列个数，即 x(2^L-2^{L-k})。

考虑莫队 + 根号分治。预处理出出现次数 >\sqrt n 的数，每次询问暴力枚举这些数计算贡献。对于其他数，令 sum_i 为出现了 i 次的数之和（注意不要取模，每次模数会变化）。枚举出现次数，计算这些数的贡献。

用光速幂即可消去一个 \log。

发现 3,4,5,6 操作其实是对连续极长 0,1 段的两端点进行修改。可以用平衡树维护这些极长段。但有可能修改产生了长度为 0 的段，可以维护最小区间长度，判断是否存在，暴力删除。

可以分开维护（标记处理较方便），也可以一起维护（推平较方便）。

分块。对于每个块，都对颜色进行一次重标号（离散化），并预处理出每块内两两颜色的最小距离、每个颜色最左 / 右的位置。

整块修改时，如果 y 没有出现，直接修改标号，距离并不会变化。如果出现了，暴力修改原数组，更新一下距离。散块暴力重构。

复杂度分析：整块修改时，如果 y 出现了，必会导致颜色数减 1，最多减 \sqrt{n} 次，每次都遍历整个块，这一部分复杂度 O(n\sqrt{n})

而散块修改最多使两个块颜色增加，这一部分 O(q\sqrt{n})