根号数据结构练习。

vvauted · 2023-11-27 10:18:58 · 个人记录

题目来源：lxl 的 ppt。

本文以题目为主，基本不涉及基础知识。

基础分块

维护一个长为 n 的序列，操作 m 次：

区间加

查询区间小于 x 的数的个数

数据范围：n, m \leq 10^5

经典问题，按 B 对序列分块，维护块内 OV。

对于修改：

整块部分打 tag，总复杂度 O(\frac n B)
散块部分直接整块重构，拿出来归并一次，复杂度 O(B)

对于查询：

整块部分直接查 OV，二分即可，总复杂度 O(\frac n B \log B)
散块枚举即可，复杂度 O(B)

总复杂度 O(mB + m\frac n B \log B)。

平衡得：B = \sqrt {n \log n} 时总复杂度最低，为 O(m\sqrt {n\log n})。

[Ynoi2017] 由乃打扑克

维护一个长为 n 的序列，操作 m 次：

区间加

查询区间第 k 小

数据范围：n, m \leq 10^5

显然查询区间第 k 小套上一个二分即转化为了上一题的查询，直接做复杂度 O(m\sqrt {n\log n}\log n)，不够快。

找找瓶颈在哪里，设对序列分块块长为 B，维护块内 OV，则有：

对于修改，这部分与上一题无异。

对于查询：

整块部分直接查 OV，二分即可，总复杂度 O(\frac n B \log B\log n).
散块枚举即可，复杂度 O(B \log n ).

考虑如何优化查询：对于整块的部分，优化是困难的；而对于散块的部分，我们相当于在重复的两个区间跑了 \log n 次暴力，不如我们直接归并构建出一个虚拟的新块的 OV，在这个新块上跑二分即可。

复杂度：O(mB + m\frac n B \log B \log n)，令 B = \sqrt n \log n，则此时复杂度为 m\sqrt n \log B。

根号平衡

维护一个长为 n 的序列，支持：

按块长为 \sqrt n 对序列分块，直接维护块内权值和即可。

维护一个长为 n 的序列，支持：

按块长为 \sqrt n 对序列分块，维护块内前缀和与前缀块权值和即可。

每次修改要维护信息的个数是 O(\sqrt n) 的，直接暴力修改。

维护一个值域 O(n) 的集合，支持：

按块长为 \sqrt n 对值域分块，维护块内插入数的个数。

查询时从第一个块往后扫一遍即可，最多进入一个散块。

维护一个值域 O(n) 的集合，支持：

按 \sqrt n 为块长对集合 OV 分块，每个块用一个长为 \sqrt n 的双端队列维护。

每次插入时可以 O(\sqrt n) 找到其所在块，O(\sqrt n) 重构该块，如果出现一个块的最后一项被挤到了下一个块，那么在下一个块的双端队列中从队头插入即可，重复这样的操作，复杂度 O(\sqrt n)

查询时运用小学数学知识可以 O(1) 找到第 k 小对应的位置。

在实现时双端队列可以换为一个环状的普通数组，维护其起点，每次从队首插入即为把起点往前移一格在这里插入，如果撞到了队尾把队尾拿出来扔到下一块里即可。

维护一颗 n 个节点的树，支持 O(1) 查 k 级祖先。

考虑预处理每个节点的 1\sim \sqrt n 级别祖先，再类似倍增维护 \sqrt n,2\sqrt n,\cdots n 级祖先，那么每次就可以 O(1) 跳到 k 级祖先了，预处理复杂度 O(n\sqrt n)。

[CodeChef] Chef and Churu

给出一个长为 n 的序列 a，给定 m 个函数 f_i，其值等于序列上 [l_i, r_i] 的区间和，操作 q 次：

对序列单点修改

求一个区间函数值的和

n, m, q \leq 10^5

按块长为 B 对函数序列分块。

维护 cnt_{x,y} 表示第 x 个块 a_y 在区间里出现了多少次，可以通过差分插入后做一次前缀和 O(m + \frac m B n) 预处理，那么修改时我们即可 O(\frac m B) 维护完所有整块的答案。

对于角块，我们可以转化为询问 O(qB) 次查询区间和，对 a 分块，套用根号平衡部分中 O(\sqrt n)-O(1) 的单点修查区间和做法即可。

平衡后总复杂度 O(m\sqrt n)

莫队

给出一个长为 n 的序列，查询 m 次一个区间每个数出现次数的平方和。

数据范围：n, m \leq 10^5

莫队板子题。维护当前区间每个出现次数和当前答案，O(1)-O(1) 的做法是显然的，复杂度 O(n\sqrt m + m)。

这里有个比较重要的结论：做莫队时 l, r 总移动次数是 O(n\sqrt m) 的，查询次数是 O(m)，也就是 n,m 同阶时修改复杂度权重远高于查询的，一般要把修改复杂度平衡到 O(1)。

[AHOI2013] 作业

给出一个长为 n 的序列，查询 m 次一个区间值在 [l_i,r_i] 中的数的个数。

数据范围：n \leq 10^5 , m \leq 10^6

差分之后是三维偏序，但是莫队能做。

在莫队的过程中我们要维护一个结构，支持快速单点加和查询一个区间有多少数。

显然使用前面根号平衡部分里的 O(1)-O(\sqrt n) 做法即可。

复杂度 O(n\sqrt m + m \sqrt n)。

[Ynoi2016] 这是我自己的发明

给你一个 n 个点的树，操作 m 次：

换根

查询两个点子树中同色点对数

n \leq 10^5, m \leq 5\times 10^5

随便拿一个点当初始根，跑一遍 dfs，询问中的子树一定可以拆成 dfs 序上至多两个区间。

易发现询问是这样一个模型：我们有一个 0/1 矩阵，每次查询一个子矩阵和。

显然查询 (l,r,L,R) 时四个关键字的询问可以差分拆成 (1, r, 1, R) 两个关键字的若干个询问。

常数比较大，容斥后每次至多拆成 4 个区间，按 lxl ppt 中说的把对询问排序换成基数排序也可以。

[Bzoj3920] Yunna 的礼物

给出一个长为 n 的序列，查询 m 次一个区间出现次数 k_1 小中值第 k_2 小的数。

数据范围：n,m \leq 10^5，卡空间。

莫队，后面第一眼做法是根号分治，出现超过 \sqrt n 次的数不超过 \sqrt n 个，那么出现次数 1\sim\sqrt n 的维护一个 O(1)-O(\sqrt n) 的值域分块，总出现次数超过 \sqrt n 的数预处理一个按权值排序的序列，一次询问遍历这至多 \sqrt n 个数，如果在区间出现次数是第 k_1 小的拿出来，最后找第 k_2 小即可。如何找第 k_1 小的出现次数呢？对出现次数序列维护一个 O(1)-O(\sqrt n) 的值域分块即可。

但是这样做的空间复杂度是 O(n\sqrt n) 的，被卡了。

我们发现出现次数可能为 1 的数的个数，出现次数可能为 2 的数的个数，\cdots ，出现次数可能为 n 的数的个数合起来是 n，那么有这么一个科技：我们把出现次数可能为 1\leq i\leq n 的所有数拿出来单独离散化一次，维护区间内出现次数为 i 的值域分块的值域为这样离散化后的值域，那么空间复杂度降至 O(n)，可以通过此题。

[Bzoj4241] 历史研究

给出一个长为 n 的序列，查询 m 次一个区间出现次数乘其值最大的结果。

数据范围：n,m \leq 10^5

莫队，根据上一题的结论，至多存在 n 种可能结果，离散化一下 O(1) - O(\sqrt n) 值域分块维护即可。

[Ynoi2015] いずれその陽は落ちるとしても

给出一个长为 n 的序列 a，定义一个区间的权值是其所有子序列的权值和，定义一个子序列的权值和是其中所有元素生成不可重集的权值和，查询 m 个区间的权值对给定模数取模的和，模数每次询问不同。

数据范围：n,m \leq 10^5

推式子，一个长为 L 的区间，x 在其中出现了 y 次，则其对区间权值的贡献是：

x\times 2^{L-y} (2^y -1)=x2^L - x2^{L-y}

如果模数相同，直接算即可，但是模数不同，要求我们计算是在线的。

前面那项是好算的，想想后面那项怎么算。

对于一个区间，不同 y 的个数是 O(\sqrt n) 的，因为 1+2+\cdots +\sqrt n = O(n)，那么我们对 y 相同的一起计算即可。

那么我们现在要处理的是：有 O(\sqrt n) 次询问，每次快速查 2^k \bmod p 的值。

显然可以找一个根号结构的东西做到：预处理 2^{i\sqrt n} \bmod p, 2^i\bmod p, i\in [1,\sqrt n)，那么每个数都可以 O(1) 拼出来。

复杂度 O(m\sqrt n)。

[HNOI2016] 大数

给出一个长为 n 的数字串 a 和一个质数 p，查询 m 次一个子串有多少个子串形成的数是 p 的倍数、

数据范围：n,m \leq 10^5

考虑维护 suf_x = a_{x, n} \bmod p ，表示 x 的后缀形成数模 p 的值，那么：

a_{l, r} \equiv \frac {a_{l, n} - a_{r+1, n}}{10^{n-r}}(\bmod \ p)

如果 p\neq 2,5，那么问题转化为求 [l, r+1] 中 suf_x 相同的位置两两相组的个数和。

否则 p=2,5 时其倍数都可以根据末尾一位判断，那么维护一个：

\sum_{i=l}^r (i - l + 1) [a_i \bmod p = 0]

即可。

[Luogu P3604] 美好的每一天

给出一个长为 n 的小写字母组成的字符串，询问 m 次一个区间有多少子区间可以重排成一个回文串。

数据范围：n, m\leq 6 \times 10^4

莫队。

一个子串可以重排为回文串等价于其中不超过一个字符出现了偶数次，因为 \Sigma 比较小，可以状压一下，那么效仿一下上题的套路，维护一个 pre_x 表示前缀有哪些字符出现了奇数次的集合，那么 [l,r] 子串合法当且仅当 |pre_r \oplus pre_{l-1}| \leq 1。

那么我们每次插入或删除 i 位时，枚举一下 |pre_i \oplus pre_{j}| ，即可找到可与 pre_i 产生贡献的 pre_j，那么开个桶维护一下插入了的 pre 即可。

复杂度 O(n\Sigma\sqrt m )。

[Ynoi2019 模拟赛] Yuno loves sqrt technology II

给出一个长为 n 的序列，查询 m 次区间逆序对数。

数据范围：n, m \leq 10^5

比较显然的 O(n\sqrt m \log n) 做法是莫队过程中拿树状数组维护值域，这个是根号平衡优化不了的，因为移动过程中既要修改也要查询，所以动态维护的做法一个 \log 是最优的。

不妨我们预处理一个的结构，支持查询区间小于 / 大于某个数的个数，这样就不用在移动的过程中插入了，可以进行根号平衡。呼之欲出的即为主席树，或者说可持久化结构，我们考虑怎么平衡它。

想要做到 O(1) 查询，那么我们做一个值域分块，维护：块内前缀权值和，前缀块权值和，那么显然一次单点加修改的信息是 O(\sqrt n) 的，我们单独直接维护整块上的信息：这部分是 O(n\sqrt n) 的，剩下的部分拿一个可持久化块状树维护，每次只需要替换掉修改位所在块上的信息即可，这部分也是 O(n\sqrt n) 的。

那么利用这种结构，我们可以做到 O(n\sqrt m) 的离线逆序对。

除了这个东西，lxl 还给出莫队二次离线的做法。

我们一次移动需要的信息即为： [l,r] 区间中小于 / 大于 x 的数的个数，那么既可以差分转化为两个前缀 l-1 和前缀 r 中大于或小于 x 的个数，我们把这个信息离线下来，扫描线后查询，那么此时插入次数是 O(n) 的，查询数是 O(n\sqrt m) 的，可以维护一个 O(\sqrt n)-O(1) 值域分块即可。

[CF765F] Souvenirs

给出一个长为 n 的序列，查询 m 次一个区间内最小 |a_i -a_j|，其中 i \neq j。

数据范围：n \leq 2\times 10^5, 1\leq a_i\leq 10^9,m\leq 10^5

离散化后值域也变成了 2\times 10^5。

第一眼莫队 + 数据结构，但是这个和区间逆序对一样，移动时需要同时支持查询和修改，很难平衡掉，且这个信息不满足可减性，没法和上一题一样差分掉去做，最好只能做到 O(n\sqrt m \log\log n)，需要一个我不会的 vEB 树。

莫队对于这道题真的不可以做吗？

如果我们存在 O(1) 插入/删除，O(1) 查询存在的数前驱后继的数据结构，那么我们就一定能做到 O(n\sqrt m)。

lxl 给出结论，在值域有界并强制在线的情况下，上文提到的 vEB 树的 O(\log\log V) 已经是确界。

但是如果我们单单去考虑删除的话，显然链表是可以做到 O(1)-O(1) 的。

我们利用一个 O(1)-O(\sqrt V) 的值域分块就能维护整体的最小值。

那么也就是说，如果我们有区间 [x,y] 的信息，想要查其子区间 [l, r] 的信息，那么就可以通过删除 (y-x+1)-(r-l+1) 次来得到我们想要的信息。

考虑我们均匀的撒 O(B) 个关键点在序列上，那么序列就被分成了 O(B) 块，我们如果我们知道任意两个关键点之间的信息，那么对于一个询问，我们找到左端点左边最右的关键点，和右端点右边最左边的关键点组成的区间，显然这两区间长度的差值是 O(\frac n B) 的，那么即可 O(m\frac n B) 处理所有的询问。

预处理 O(B^2) 种信息是不现实的，考虑我们离线把询问分配给左端点后，在线的去处理这些询问，我们预处理每个块内值域分块的信息以及链表，那么使用归并合并链表即可以做到对于单个左端点 O(n)，总共 O(nB) 的复杂度得到需要的关键点的信息，这样做需要支持回撤操作，维护一个操作栈即可。

总复杂度 O(m\frac n B + m\sqrt V+ nB)，平衡后复杂度 O(n\sqrt m)。

这个莫队做法即为广为周知的回滚莫队。

有 \text{polylog} 做法，link，我随便搜出来的。

[Bzoj4358] permu

给出一个长为 n 的序列，查询 m 次一个区间中最长的值域连续段。

值域连续不意味着在序列上也连续。

数据范围：n,m \leq 10^5

显然可以直接维护值域连续段，加入一个数 x 是简单的，只需要合并 x-1,x, x+1 所在的值域连续段即可，但是由于最终取得是 max，删除是困难的，套用回滚莫队的做法即可。

[CodeChef] QCHEF

给出一个长为 n 的序列，查询 m 次一个区间中值相同时位置差的最大值。

数据范围：n,m \leq 10^5

开一个桶，维护区间中上每种值出现的最左点和最右点，同样的，由于取的是 \max 不具有可减性，套用回滚莫队的做法即可。

[Cnoi2019] 数字游戏

给出一个长为 n 的排列，查询 m 次一个区间多少个子区间的值都在 [x,y] 内。

数据范围：n,m \leq 10^5

考虑对值域莫队，那么我们有一个结论：把在当前值域区间里的数染色，那么最后答案就是所有极长被染色区间中两两匹配数之和。

那么如何维护极长 1 段的信息呢？第一个想到的显然是 O(\log n)-O(\log n) 的线段树。思考一下如何把这个复杂度根号平衡掉，我们对序列分块，维护和线段树一样的分治信息：段内答案和以及和块左右断点链接的极长染色段长度，那么之前维护值域连续段的做法套用到这题上即可。

静态分块基础

[Ynoi2019 模拟赛] Yuno loves sqrt technology I

给出一个长为 n 的序列，查询 m 次区间逆序对数，强制在线。

数据范围：n, m \leq 10^5

既然都会了莫队做法，来想想在线的分块做法。

设我们以 B 为块长对序列分块。

角块块内的贡献显然可以预处理，角块一定是一个整块的前缀或后缀，那么从每一块块首/尾跑一次逆序对，树状数组维护，既可做到 O(n\log n) 预处理 O(1) 查。

用前面题目 O(n\sqrt n) 预处理 O(1) 查询区间大于或小于 x 的数的可持久化分块可以把角块部分的权值化掉，不过这种做法的常数有点大。

考虑另外一种，我们每个块预处理一个值域分块， O(\sqrt n) -O(1) 的块内小于或大于 x 的数的个数的信息，然后再对所有块做一个前缀和，那么角块-整块部分的贡献就 O(B) 解决了。角块-角块的部分，我们预处理块内 OV 然后归并即可 O(B) 求出。

那么我们现在要处理的就是整块-整块的贡献，这部分的贡献有 (\frac n B)^2 种，考虑这部分我们去暴力预处理，把第 r 块当做角块，[l, r - 1] 块的结果可以 O(B) 转移至 [l, r] 块的结果，那么这部分则是 O(\frac{ n^2} B) 的。

整块块内的贡献暴力算显然是正确的。

如果仅仅需要 O(\frac {n^2} B) 的块之间的贡献还可以用容斥：

f(l,r) = f(l + 1, r) + f(l, r - 1) - f(l + 1, r -1) + calc(l,r)

其中 calc(l, r) 指 l, r 两块产生的逆序对数，显然可以 O(B) 归并得到，不需要预处理，常数比较小。

平衡后，复杂度 O(n\sqrt m)。

[CF765F] Souvenirs 加强版

给出一个长为 n 的序列，查询 m 次一个区间内最小 |a_i -a_j|，其中 i \neq j，强制在线。

数据范围：n \leq 2\times 10^5, 1\leq a_i\leq 10^9,m\leq 10^5

既然都会了莫队，想想在线的分块做法吧，设按块长为 B 将序列分块，显然这个东西还是有可加性的，继续拆成角块 - 角块、角块 - 整块、整块 - 整块、角块块内和整块块内五部分。

角块-角块的部分一次归并即可算完。

由于没有可差分性，角块-整块如果看成 \sqrt n 次区间查询是难做的，那么不妨把每个整块的贡献分开算，我们预处理 f_{x, y} 表示第 x 位与第 y 个块形成的贡献，这部分信息 O(\sqrt n)-O(1) 平衡是平凡的，那么总共有 O(\frac {n^2} {B}) 对 f，复杂度 O(\frac {n^2} B)，块内做前缀/后缀和（当然这里的和定义为取 \max），那么角块一定可以拆成一段块的前缀，一段块的后缀，共 O(\frac n B) 个块，这部分复杂度 O(\frac n B)。

整块-整块的做法可以效仿上一题的做法，其实和角块-整块的做法是本质相同的，抄过来而已，复杂度 O(\frac {n^3}{B^3}) 预处理，单次查询 O(1)。或者可以写出来以下式子：

f(l,r) = f(l + 1, r) + f(l, r - 1) + calc(l,r)

因为这里的加法也就是 \max 是不需要不重的，l,r 块的贡献归并即可。

整块块内的贡献直接暴力复杂度也是对的，角块块内直接拿 polylog 结构预处理，最多操作 O(n) 次，复杂度也是对的。

平衡后我们有 O(n\sqrt n) 的强制在线分块做法。

[Ynoi2019 模拟赛] Yuno loves sqrt technology III

给出一个长为 n 的排列，查询 m 次区间众数，强制在线。

数据范围：n,m \leq 5\times 10^5

考虑分块，按块长为 B 对序列分块。

对于角块，我们需要一个 O(1) 查区间某数出现个数的结构，这个东西具有可减性，用上面说到的可持久化块状树或者是预处理前缀块某个数出现的次数都是可行的。

对于整块的部分，还是套用角块的做法，预处理任意两块之间的众数，复杂度 O(\frac {n^2} B)。

那么这样平衡后复杂度 O(n\sqrt n)，但是空间复杂度同样也 O(n\sqrt n)，被卡了。

考虑角块的部分最多让整块部分的答案增加 O(\sqrt n) 次，那么我们把角块维护成一个序列，每次我们只需要判断现在的数的出现次数是否大于当前 ans，如果大于的话给 ans 加一即可，否则删去，那么我们至多判断 O(\sqrt n) 次。

我们对于每个颜色维护一个其所有在序列中出现的下标 OV，那么每次判断区间中出现次数是否大于 x，只需要判断其在 OV 里下标往前 x 个是否还在区间中即可，单次 O(1)，每次询问总复杂度 O(\sqrt n)，总空间复杂度 O(n)，可以通过此题。

根号平衡

给出一个 n 条节点 m 条边的无向图，处理 q 次操作：

修改一个点的点权

查询与一个点相邻所有点的点权和。

数据范围：n,m,q\leq 10^5

我们考虑总边数为 $m$，那么度数超过 $\sqrt m$ 的点不超过 $\sqrt m$ 个，可以根号分治，我们修改的时候仅维护这 $\sqrt m$ 个点的点权，查询时如果度数超过 $B$ 则 $O(1)$ 查询已经维护了的值，否则暴力加一遍，复杂度 $O(\sqrt m)$，总复杂度 $O(q\sqrt m)$。 ------------ > 给出一个长为 $n$ 的序列 $a$，查询 $m$ 次，每次给出 $x,y$ 查最小的 $|i-j|$ 满足 $a_i = x, a_j =y$。 > > 数据范围：$n,m\leq 10^5

考虑我们对每个颜色维护其在序列中下标的 OV，那么单次查询使用归并复杂度即为 O(\max(cnt_x,cnt_y)) 的，其中 cnt_x 代表 x 在序列中出现的次数。

一个很典的性质是出现次数超过 \sqrt n 的数不超过 O(\sqrt n) 个。

那么我们对于出现次数 \leq \sqrt n 的颜色，我们直接归并查的复杂度是 O(\sqrt n) 的，剩下的 O(\sqrt n) 个出现次数超过 B 的颜色，我们预处理其与其他所有颜色的答案，只需要正反扫两遍序列，每种颜色维护一个桶，表示上一次最近出现的位置即可，复杂度 O(n\sqrt n)，单次询问 O(1)。

那么也就是我们把问题拆成了两个部分，一部分的颜色数比较小，用关于颜色数的做法去做，另一部分的出现次数比较小，用另一个关于出现次数的做法去做，把一个问题拆分成了两个子问题，分类解决。

[IOI2009] Regions

给出一个 n 个节点的树，每个树有一种颜色，询问 m 次，每次给出两种颜色 r_1,r_2，求有多少点对 (e_1,e_2) 满足 e_2 是 r_1 色的，e_2 是 r_2 色的，且在树上 e_1 是 e_2 的祖先，强制在线。

数据范围：n, m\leq 10^5

对于一次询问，易发现其等价于 cnt_{r_1} 次询问，每次询问一个子树有多少个 r_2 色的，最后求和。

子树查询易转化为 dfs 序上的区间查询，考虑这些询问是可以看离线的，我们把 cnt_{r_2} 色的单独拿出来，那么把每个询问区间差分，每次 O(1) 插入，再做一次 O(cnt_{r_2}) 前缀和即可算出每一个 r_2 色节点的贡献，复杂度 O(cnt_{r_1} + cnt_{r_2})。

和上题一样的套路，cnt 超过 \sqrt n 的颜色最多 \sqrt n 种，预处理这些颜色做 r_1 或者 r_2 时的答案，每种颜色两次 dfs 即可算出，总复杂度 O(n\sqrt n)，单次查询 O(1)，没有预处理的情况直接拿出来算即可，单次查询 O(\sqrt n)，总复杂度 O(m\sqrt n )。

[SHOI2006] Homework

维护一个集合 S，操作 m 次：

在 S 中插入一个 x，保证 x 不属于当前集合。

给出 y，询问当前集合对 y 取模的最小值。

数据范围：m,V\leq 10^5，其中 V 是 x,y 的值域。

有 O(V)-O(1) 或者是 O(\sqrt V)-O(\frac V y) 的做法。

$O(\sqrt V)-O(\frac Vy)$ 的做法则需要 $O(\sqrt V)-O(1)$ 维护值域区间出现的最小数，维护一个值域分块根号平衡即可。这个怎么平衡呢？我们维护每一个块后缀出现的最小数，再维护每一个块左端点右侧的出现的最小数即可，每次修改只需要维护 $O(\sqrt V)$ 的信息，查询时答案即为第一个整块维护的左端点右侧的出现的最小数与区间左端点块后缀出现的最小数取 $\min$，当然如果超过了询问区间这一段就没有值了。那么根号平衡，维护小于 $\sqrt n$ 模数的答案，否则直接询问 $\sqrt n$ 次即可。 ------------ > [POI2015] Odwiedziny > > 给出一个 $n$ 个节点的树，查询 $m$ 次从 $x$ 每次跳 $k$ 格到 $y$ 形成的路径的权值和，保证可以跳到。 > > 数据范围：$n,m\leq 10^5

按对于询问，按每个节点深度 \bmod \ k 分类，显然 x,y 必属于同一类，且同类中生成树上其路径就是我们要求的路径。

那么对于 k < \sqrt n，我们按分的类，建 O(k) 个，总大小 O(n) 的树，支持 O(1)-O(\sqrt n) 查询一个树路径上的信息即可，这个是很容易做到的，或者如果没有强制在线的话，把询问离线下来直接跑 O(\sqrt n) 遍 dfs 即可。

如果 k > \sqrt n，路径上的点数是小于 O(\sqrt n) 的，根号平衡维护一个 O(1) 的 k 级祖先即可。

[Ynoi2015] いまこの時の輝きを

给出一个长为 n 的序列，查询 m 次一个区间乘积的约数个数 \bmod 19260817 的结果。

数据范围：n,m\leq 10^5,V\leq 10^9，其中 V 代表值域。

直接莫队的话，考虑每个数只有 O(\log V) 种质因数，总共至多 O(n\log V) 种，这个上界是远远不满的，事实上是 O(\frac {\log V} {\log \log V}) 的，且对于约数个数来说，质因数之间相互没有影响，那么离散化后有 O(n\sqrt m \log V) 的莫队做法。

大于 N^{\frac 1 B} 的质因数最多有 B - 1 个，令 B = 3，则我们对于 V^{\frac 1 3} 的质数单独维护一个前缀出现次数，这部分为 O(n\frac {V^{\frac 1 3}}{\log V}) 的，剩下的大于 V^{\frac 1 3} 的质因数我们离散化之后用莫队维护即可，每个数最多有两个，则莫队部分是 O(n\sqrt m) 的。

我们还需要快速的质因数分解，需要 Pollard-Rho 算法。

根号重构

给出一个 n 个节点带点权的树，操作 m 次：

link / cut 一条边。

查询路径第 k 小点权。

数据范围：n, m \leq 10^5

如果没有 link / cut，显然可以用可持久化 01 trie O(m\log n) 维护，假如进行了 x 次 link / cut，那么这条路径一定可以拆为 x 条原树上的路径 O(x\log n) 求出，那么不妨我们 \sqrt m 次操作重构一次 01 trie，那么单次询问复杂度 O(\sqrt m \log n)，单次重构复杂度 O(n\log n)，总复杂度 O(n\sqrt m\log n)。

实际上实现还是复杂的。

怎么就这一道题了？？

树上分块

Count On Tree

给出一个 n 个节点的树，每个节点有一种颜色，查询 m 次查询一条路径上的颜色数。

数据范围：n, m \leq 10^5

序列区间数颜色做法是平凡的，直接括号序然后转为序列上的莫队问题即可。

如果强制在线，考虑树上分块做法，我们在树上随机撒 \sqrt n 个点作为关键点，预处理两两之间答案，那么我们每次查询，对于路径的两个端点向上找到第一个关键点，那么期望走过的距离是 O(\sqrt n) 的，这部分即为角块。我们只需要一个快速判断一个路径是否出现某种颜色即可。

是否出现是不可减的，有点难做，考虑维护一个出现了多少次某种颜色，那么通过可持久化结构做到 O(\sqrt n) - O(1) 是简单的，但是难写。考虑我们预处理一个 f_{x,y} 表示第 x 块出现了多少颜色为 y 的点，再对块那维做个前缀和，即可 O(1) 询问，先把两个角块的颜色合起来并去重即可。

例题

[Ynoi2010] D1T2

维护一个长为 n 的颜色序列，操作 m 次：

区间染色。

查询选出区间两数颜色相同的方案数。

数据范围：n, m\leq 10^5

对序列分块，块长为 B。

莫队带修复杂度是不怎么好的，考虑没有染色的分块做法，我们预处理前缀块某种颜色的出现次数，预处理一段块的答案，那么对角块开桶计数之后即可 O(B) 算出角块的贡献。

那么考虑如何染色？考虑一次染色只有角块染不满整块，那么这种填不满整块的颜色段数是 O(m) 的，如果一个块被染满则维护整块的颜色，否则维护块内颜色段即可。

对于被染满色的整块，其性质和角块是近似的，单独出来维护即可。

那么现在问题是，如何在某个块添加/删除一个颜色段后高效维护信息。

对于前缀出现某个颜色的次数，一次添加/删除影响的信息是 O(\sqrt n) 的，直接维护即可。对于某段块的答案，把其当成 \sqrt n\times \sqrt n 的一个矩阵，每次影响的位置个数是 O(n) 的，显然无法直接修掉，那么考虑如果我们修的是第 x 块，对于 ans_{l,r} 实际上的影响是分成两段的：这段与 [l,x-1] 块形成的贡献与 [x +1,r] 块形成的贡献，也就是行列是互相独立的，那么考虑行列分开维护，第 r 行中修改 [x+1, n] 列的贡献都是相同的，我们差分掉即可拆成 O(\sqrt n) 次单点修，每次询问只需要查单点权值，也就是只需要查一行一列的单点，用 O(1) - O(\sqrt n) 的根号平衡维护即可。

不过如果不做前缀和，换成每次修行列查矩阵和也是简单的。

[Ynoi2011] D1T1

维护一个长为 n 的序列 a，操作 m 次：

对 i \bmod x=y 的所有 a_i 加 z。

查询区间和。

数据范围：n, m\leq 10^5

根号分治。

对于大于 \sqrt n 的 x 暴力单点加，单次最多加 O(\sqrt n) 次，维护一个 O(1)-O(\sqrt n) 的前缀和即可。

对于小于 \sqrt n 的 x，对于 x 相同的修改我们一起维护，我们按模 x 分成 x 个同余类，两两同余类不互相影响，且同余类内修改对其的贡献相同。那么一个区间显然可以拆成若干个组同余类，还有两个角块，那么我们再维护一个前后缀和，显然每次修改暴力改前后缀和也是 O(\sqrt n) 的，则每次询问遍历 x = 1\sim \sqrt n 单次 O(1) 查询每个 x 的答案，再 O(\sqrt n) 查询一次 x\geq \sqrt n 整体的答案即可。

复杂度 O((n+m)\sqrt n)。