Euclid’s lemma

若素数$p$为$ab$的约数，那么$p$至少是$a$，$b$这两个数中的一个数的约数。也就是说，$p\mid ab,p\not\mid a \Rightarrow p\mid b$。

它还有一个推广：

问题：求$C_n^m\mod p$，其中保证$p$为质数。

将$n,m$进行$p$进制展开：

则有

我们有$Bell$数的递推式：

设$B(x)$为它的指数生成函数，也就是$B(x) = \sum_{i=0}^{\infty} {b_i\over i!}x ^i $。

考虑

有一个序列，序列中的每一个元素有两个值$h_i$与$val_i$。你需要回答若干次询问，每一次询问针对于一个区间$[l,r]$，设$l\le p_1<p_2\cdots p_k\le r$，其中$p_k$是$[l,r]$中$h_i$最大的位置，$p_{k-1}$是$[l,p_k-1]$中$h_i$最大的位置……你需要回答出这些位置的$val_i$的某些可以区间合并的信息（和/最大最小值……）。

可以对序列中元素的$h_i,val_i$进行修改。

定义 & 结构

连续段

• 对于一个排列$A$，我们定义$[l,r]$是连续段，当且仅当这个区间的值域也是连续的一段。即，不存在$x,y,z$，$x,y\in [l,r]\wedge z\not\in [l,r]\wedge A_x < A_z < A_y$。也等价于$\max \{ A_k \mid k\in [l,r] \} - \min \{ A_k \mid k\in [l,r] \} = r-l$。
• 连续段有一个很好的性质：考虑两个相交且不互相包含的连续段$x,y$，总有$x\cup y$、$x\cap y$、$x\setminus (x \cap y)$、$y\setminus (x\cap y)$是连续段。

参考：一篇cf上的很好的blog

食用方法：树上路径数颜色。

我们构造一棵树的括号序：即，dfs一棵树的时候，在发现一个节点时，记此时的$idx$为这个节点的$In$，然后让$idx++$；结束对一个节点的访问时，记此时的$idx$为这个节点的$Out$，然后让$idx++$。这样，$u$和$v$之间路径，就转化括号序中的区间$[Out_u,In_v]$，其中我们要求区间中出现了$0$次或者$2$次的节点都不计贡献（说白了就是挪指针的时候进行类似异或的操作），即：

treap

treap，又叫树堆。我们可以用它去维护一个序列，或者一个集合。裸的带旋的treap可以支持插入，删除，查第$k$大，查排名，以及其他的二叉搜索树的操作；无旋treap可以支持所有splay支持的操作（区间修改，翻转，覆盖，信息合并等等），操作的复杂度是$O(\log n)$的，并且不是均摊的！

2016集训队论文集 吉如一《区间最值操作与历史最值问题》

1 hdu5306 Gorgeous Sequence

维护一个长度为$n$的序列，支持以下操作：
$0 l r t$：对于所有$i \in [l,r]$，将$a_i$修改为$\min \{ a_i,t\} $。
$1 l r$：查询区间$l,r$的最大元素的值。
$2 l r$：查询区间$l,r$元素的和。

LCT

前言

LCT用来维护的是森林。它可以支持加边（link)、删边（cut）、链信息修改和查询、子树信息查询。

参考资料

1. OI-wiki
2. wikipedia
3. 一份有详细图解的课件

KD-Tree 是什么