AC自动机
-
解决多模式串的匹配问题，本质上是Trie树+KMP。
-
构造：首先建一棵Trie树，然后构造nxt数组。当我们遍历到u时，让它的nxt数组指向u的父节点的nxt指针具有相同字母的子节点（第一层直接指向根）。匹配时如果当前字符匹配失败，利用nxt数组进行跳转。最后扫描统计答案。
-
常见用法：n个单词，和长为m的文章。有多少个单词在文章中出现过。
CDQ分治
-
转化离线问题
-
实现：在分治开始前对a数组进行排序，处理b数组时分治，左右区间分别递归处理，左跨右区间用双指针处理，c数组则用树状数组解决。
-
常见用法：通常处理三维偏序问题。
整体二分
-
思考：先想单个的问题怎么求，在想整体怎么求，把问题整合在一起。
-
实现：二分答案，在树状数组上把二分答案的贡献加进来。对于每一个问题，看看它查询的区间，将这些问题分为达标和不达标（不达标的组，查询的要求变小），然后继续二分直到结束。
-
整体二分将所有问题，查询捆绑在一起解决，比单个问题一个一个解决快了很多。
还需继续做题，进行实际运用。