KMP

KMP的出现优化了在字符串中查找子串的过程。使复杂度达到$O(m+n)$

定义

题意

• 给定 $n$ 个结点的无向完全图。每个点有一个点权为 $a_i$。连接 $i$ 号结点和 $j$ 号结点的边的边权为 $a_i\oplus a_j$。
• 求这个图的 MST 的权值。
• $1\le n\le 2\times 10^5$，$0\le a_i< 2^{30}$。

例题

引入

引入1：积性函数

中国剩余定理

定义

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中 $n_1, n_2, \cdots, n_k$ 两两互质）：

题目背景

题目描述

如题，你需要维护这样的一个长度为 $N$ 的数组，支持如下几种操作

1. 可持久化数组
2. 可持久化线段树(主席树)
3. 可持久化字典树(01Trie)
4. 可持久化平衡树