树上莫队-笔记 /「SPOJ 10707」COT2-题解
通过SPOJ 10707 COT2-Count on a tree II这道题目来学习一下 树上莫队
当需要离线查询 树上 的多区间问题时,可以使用 树上莫队 来解决
主要通过 欧拉序 将树转化为一条链,然后在链上执行普通莫队的操作
通过SPOJ 10707 COT2-Count on a tree II这道题目来学习一下 树上莫队
当需要离线查询 树上 的多区间问题时,可以使用 树上莫队 来解决
主要通过 欧拉序 将树转化为一条链,然后在链上执行普通莫队的操作
通过AtCoder 1219 歴史の研究这道题目来学习一下 回滚莫队
回滚莫队 适用于容易进行add
操作,而不容易实现del
的情况
通过莫队的分块,指针移动的思想,可以让左指针进行回滚操作, 近似 达到del
的效果
通过Luogu P1903 数颜色/维护序列这道题目来学习一下 带修莫队
顾名思义,带修莫队 不仅要支持普通莫队的查询操作,还要支持数据中途的修改
比如这道题目,需要实现以下目标
达到这个目标,可以在普通莫队的基础上加一个时间维度,实现 带修莫队
这篇文章来记录一下莫队算法时间复杂度的简单(不严谨)计算
首先分析一下莫队算法的时间复杂度有哪些方面构成
Query
数组的排序$dsu\ on\ tree$($disjoint\ set\ union\ \text{on tree}$)算法,也称 __树上并查集__。使用了并查集的按秩合并(启发式合并)的方法,结合 树链剖分 中的 轻重儿子划分 ,对 树上暴力统计 进行了优化。使用这个算法需要满足以下两个条件:
左偏树($Leftist\ Tree$),是一种 __可以合并的堆状结构__,支持以下操作
树状数组($Binary\ Indexed\ Trees$)是一个维护__前缀和__的数据结构,需要支持以下操作
模板地址: GitHub
1 | LL gcd(LL a, LL b) { |
lcm(a, b) = a / gcd(a, b) * b
目标: 寻找一对整数$(x, y)$,使$ax+by=gcd(a,b)$
1 | void exgcd(LL a, LL b, LL& d, LL& x, LL& y) { |
$ax+by=c$且$x,y$全为正整数,则当且仅当$gcd(a, b)|c$
1 | bool vis[maxn]; |
1 | void getprime(int n) { |
$$
\pi(x) \sim \frac{x}{\ln x}
$$
原理:费马小定理
若$a^{n-1}\equiv 1\pmod n$,$a$取值越多,可以近似认为$n$为质数
使用二次探测定理改进卡卡迈尔数(合数$n$对于任何正整数$b$,都满足$gcd(b, n)=1\ \ b^{n-1}\equiv 1\pmod n$)的bug
1 | LL Random(LL n) { return (LL)((double)rand() / RAND_MAX * n + 0.5); } |
$$
(a + b)\bmod n = ((a\bmod n) + (b\bmod n))\bmod n\\
(a - b)\bmod n = ((a\bmod n) - (b\bmod n) + n)\bmod n\\
ab\mod n = (a\bmod n)(b\bmod n)\bmod n
$$
1 | LL mul_mod(LL a, LL b, LL n){ |
1 | LL pow_mod(LL a, LL p, LL n) { |
使用位运算:
1 | LL pow_mod(LL a, LL p, LL n) { |
$$\varphi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_k})$$
$\varphi(n)$表示不超过$n$且与$n$互质的整数个数
1 | int euler_phi(int n) { |
1 | int phi[maxn]; |
若$gcd(a, n) = 1$,则$a^{\varphi(n)}\equiv 1\pmod n$
若$p$为质数,则$a^{p-1}\equiv 1\pmod p$
若$p$为质数,则$(p-1)!\equiv -1\pmod p$
$$a\div b\bmod n = a\times b^{-1}\bmod n$$
$b^{-1}$称为$b$在模$n$意义下的逆元
使用费马小定理, $a^{-1} = a^{n - 2}$
递归求解
1 | LL inv(LL a, LL n) { |
1 | int inv_table[maxn]; |
$ax\equiv b\pmod n$可以化为$ax+ny=b$使用扩展欧拉定理解决
求解$x\equiv a_i\pmod {m_i}$满足$m_i$两两互质
1 | LL crt(int n, int* a, int* m) { |
$m_i$不一定两两互质
1 | LL excrt(LL n, LL* a, LL* m) { |
求解$a^x\equiv b\pmod n$满足$n$为质数
1 | int log_mod(int a, int b, int n) { |
整除分块可以对后面的莫比乌斯反演提供很大的优化
通过枚举可以发现$\lfloor \frac{n}{i} \rfloor$的结果会出现分块现象
例如$n=10$时
$\ \ \ i\ \ \ \ 1\ \ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\ 11\ 12\ 13\ …$
$\lfloor \frac{n}{i} \rfloor\ 10\ 5\ 3\ 2\ 2\ 1\ 1\ 1\ 1\ 1\ \ \ 0\ \ \ 0\ \ \ 0\ \ \ …$不难发现,每个块的右端点为$r=\lfloor \frac{n}{t}\rfloor (t=\lfloor \frac{n}{i}\rfloor)$
$$
\mu(n) =
\begin{cases}
1, & n=1 \\
(-1)^r, & n=p_1p_2p_3…p_r(\text{$p_i$为互不相同的质数}) \\
0, & else
\end{cases}
$$
性质:
$$\sum_{d|n}{\mu(d)}=[n=1]$$
$$\sum_{d|n}{\frac{\mu(d)}{d}}=\frac{\varphi(n)}{n}$$
线性筛:
1 | int mu[maxn], vis[maxn]; |