Dancing Links缩写为DLX，其实在竞赛中并不常见，这次会讲这个是因为前一阵子搞拼图写了这个数据结构就顺便写(水)博客。
DLX的发明者是高德纳（Donald Knuth），就是那个传说中的《计算机程序设计艺术》（TAOCP）系列书的作者，这里对这个算法做一些比较直观的解释。
DLX面向的问题 DLX面向的问题是精确覆盖问题。何谓精确覆盖呢，来看以下这个表格，每一行是一个数组，数组有4个元素，每行的第一列是这个数组的名字
name a 0 0 0 1 b 1 0 0 1 c 1 1 0 0 d 1 0 1 0 e 0 1 1 1 f 0 0 1 0 g 0 1 0 1 我们的目标是，在这些集合里，挑出几个，例如我们挑a,b,c，那对应位置上的元素相加，于是得到 2 1 0 2。而我们的目标是，找到一个挑选的方法，使得相加得到 1 1 1 1 全是1。
例如说，选 d和g，那么相加正好得到 1 1 1 1 ，这就是其中一个解，这就是精确覆盖问题的直观感知。
回文树（EER Tree，Palindromic Tree），有点类似Trie，但它并不是匹配字符串的，很多人称之为回文自动机，但它一点也不像自动机，不过我还是按习惯的来，使用PAM为简称。为了表示一个回文，我们只表示一边的一个单链即可，这时就类似Trie。但不同之处是，回文区分奇数长度和偶数长度，所以这里我们使用两个根，分别来表示奇数长度和偶数长度。所以，在奇数根里，链ba表示aba，而在偶数根里的ba表示abba。
首先我们来直观地看看PAM的图形化，以下是字符串abcbbc的PAM
graph TD; linkStyle default interpolate basis subgraph root 0-.->1[-1] end subgraph node0 0-->6((bb)) 6-->7((cbbc)) end subgraph node1 1-->2((a)) 1-->3((b)) 1-->4((c)) 4-->5((bcb)) end 2-.->0 3-.->0 4-.->0 6-.->3 5-.->3 7-.->4 style 0 fill:#f9f style 1 fill:#f9f 实线方向就是子节点方向，虚线是fail指针，指向这个节点最长的回文后缀节点。图有点乱，但又不希望画得过于简单导致说不清楚，将就一下吧。
后缀自动机（SAM），可以结合前文的AC自动机一起理解，所谓后缀自动机，就是把一个字符串的所有后缀构造AC自动机，即只匹配其后缀的自动机。但是作为一个字符串的所有后缀，与一般的AC自动机有些不一样的性质，直接构造AC自动机，节点数是 $O(n^2)$，而SAM则对重复的节点合并了，可以让节点数大幅下降到 $O(n)$。
首先我们来直观地看看SAM的图形化，以下是字符串abcac的SAM
graph LR; linkStyle default interpolate basis 0((0))--a-->1 1--b-->2 2--c-->3 3--a-->4 4--c-->5((5)) 0--c-->6(1) 0--b-->2 1--c-->5 6--a-->4 4-.->1 5-.->6 3-.->6 1-.->0 2-.->0 6-.->0 style 0 fill:#f9f style 5 fill:#f9f 实线方向就是匹配方向，虚线与AC自动机中的失败指针非常像，在SAM里称为link指针。
听到AC自动机很多人第一次听到的反应往往是很兴奋的。但其实并不是你们想的那种东西。它的全称是Aho-Corasick algorithm，另外，自动机的英文是Automaton，所以AC自动机即 AC Automaton。为了解释这个算法，首先我们来回顾KMP，你需要很理解KMP的原理，不然看后面的内容就会变得妙不可读。
KMP自动机 本质上KMP其实就是一种自动机。这次我们改用自动机的形式来理解。所谓自动机，一般指的是确定有限状态自动机，你可以看作一个黑箱，每次输入一个数据，它就会改变它的内部状态，并有相应的输出。如果你知道Trie，那么它其实就是一个典型的自动机。我们还是拿字符串abacabab作为例子，如果是生成next数组，结果如下：
string a b a c a b a b \0 next -1 0 0 1 0 1 2 3 2 为了方便变成自动机的方式理解，我们把这个改成有向图
graph LR; linkStyle default interpolate basis 0[Start]--a-->00[1] 00--b-->1[2] 1--a-->2[3] 2--c-->3[4] 3--a-->4[5] 4--b-->5[6] 5--a-->6[7] 6--b-->7[8] 00-.->0 1-.->0 2-.->00 3-.->0 4-.->00 5-.->1 6-.->2 %%7[b]-.->3[c] style 0 fill:#f9f,stroke-dasharray: 5, 5 style 7 fill:#f9f,stroke-dasharray: 5, 5
可持久化权值线段树，wiki上指出引入者名字叫黃嘉泰，名字缩写正好是某位主席名字，所以又叫做主席树。而本篇先介绍可持久化线段树，阅读本篇前你需要先了解线段树
概念 所谓的可持久化，意思是你能得到所有的历史版本，为了达到这个效果，当然可以每次修改的时候，先整体复制再修改，结果自然就是会爆内存。而事实上，由于每次修改最多改一条链，而其它分支可以重用。我们先拿链表做例子，如果有个链表内容是 1->2->3->4->5 ，现在我们把3修改成6，得到 1->2->6->4->5 ，但是后面的元素没有改动，所以我们可以把后面的元素直接重叠在一起使用，如下图：
graph LR; 1-->2 2-->3 3-->4 4-->5 1'-->2' 2'-->6 6-->4 这样，完全可以当成两条不同的链表使用，同时节省空间。而可持久化线段树做法与这一样，就是没变的部分还使用原来节点，所以这个实现不能使用之前介绍的堆式储存，要和平衡树一样动态开节点。
数据结构 假设我们的数据是以下这样
下标 1 2 3 4 数据 1 0 5 2 构建线段树后结果如下
graph TD; 1,4:8-->1,2:1 1,4:8-->3,4:7 1,2:1-->1,1:1 1,2:1-->2,2:0 3,4:7-->3,3:5 3,4:7-->4,4:2 冒号前面的两个数表示一条线段，冒号后表示的是数据，这个数据表示的是这个区间的和。
然后我们要把第3个元素从5改为1，构造第二棵线段树，首先复制一个root，包括儿子的指向也复制，得到
graph TD; 1,4:8-->1,2:1 1,4:8-->3,4:7 1,2:1-->1,1:1 1,2:1-->2,2:0 3,4:7-->3,3:5 3,4:7-->4,4:2 1,4':8-->1,2:1 1,4':8-->3,4:7
讲完了treap和splaytree，接下来讲把这两的思想混合在一起的 FHQ Treap，据说作者是范浩强。
splay其实还有两个操作split和merge没有介绍，我打算把这两放在这里一并介绍
Split和Merge Split就是把树按某个条件划分成两棵子树，如果是查找树，就按某个值划分为小于它的以及大于等于它的（等于号取哪边怎么好写怎么来就是），如果是序列维护，那就按照rank来划分。而merge操作则正好相反，把两棵子树合并成为一棵。所以，如果我们需要对某个区间做操作，那么我们就把那个区间Split出来，操作好了后（打懒惰标记，或取出结果）再Merge回去就行了，与splay操作的思路是差不多的。不过为了在split再merge后能间接对树的平衡性优化，我们不能简单地merge，要套用Treap的随机数法，我们先来看怎么split。
先定义好接口void split(int tp, int k, int &x, int &y)，x是返回的左子树，y是返回的右子树，接着我们需要递归split，如果划分点在左子树，那么y一定是根，反之划分点在右子树，那么x一定是根。确定了其中一个，在递归调用的时候，假如y确定了，于是还没确定的，就是x以及根节点的左子树的指向，所以把这两传参就行了，时间复杂度 $O(logn)$ ，具体代码如下：
// 维护序列的实现 void split(int tp, int k, int &x, int &y) { if (!tp) { x = y = 0; return; } pushdown(tp); if (k <= nodes[ch(tp, 0)].sz) { y = tp; split(ch(tp, 0), k, x, ch(tp, 0)); update(y); } else { x = tp; split(ch(tp, 1), k - nodes[ch(tp, 0)].sz - 1, ch(tp, 1), y); update(x); } }
平衡树除了用来对存在偏序关系的数据进行维护，还能用于对序列维护，相当于一个数组。阅读本文你需要先看完上一篇关于treap的文章。
序列维护 在之前的文章，我们介绍过使用树状数组，以及线段树来维护一个序列，可以做区间操作及区间求和，但它们都存在一个缺点，不能动态插入数据。那我们怎么样才能通过平衡树来维护序列呢，之前我们有一个size字段能快速找第k大（或树的中序遍历第k个元素），而旋转操作并不会改变元素之间的相对顺序，那么我们就通过它直接插入到第k个元素的前面，这样我们插入的时候就不再通过要插入的值本身的大小关系，而需要多加一个参数k决定插入的位置。当平衡树用于维护序列的时候，就不用考虑元素相等的问题了。这样我们把元素相等处理的代码删除并修改基本操作的代码就能得到第一个能维护序列的基本模板，以下模板使用Treap修改得来。
这里之所以把这两个放在一起讲，是因为它们实在是相似度很高（至少在竞赛领域），都需要求kth和指定元素的rank（Treap的话可有可无，但通常会需要）。不过如果你没有写过树，强烈建议你自己通过理解来写一遍。
BST 首先，Treap和SBT都属于BST的一种，BST就是二叉搜索树，它满足的特点是：
二叉树 没有两个节点的值相等 任意子树的根节点的值都比左子树所有节点的值要大 任意子树的根节点的值都比右子树所有节点的值要小 任意子树均为二叉搜索树 如果我们实在需要支持多个相同值放在树里面，那么有两种情况，如果那些相同值是确实完全没有区别（例如int），那么只需要在每个节点多加一个字段记录这个值出现的次数就可以了，但如果这些值只有偏序关系，可能不是严格相等，存在其它非比较字段，那么我们就再在每个节点增加一个next域做成一个链表即可。
很多人在初始接触线段树的时候，一看到别人写一大堆代码就直接弃坑了，其实不要被它的外表所欺骗，线段树其实是相当好写的树结构了，而且理解起来其实很简单。要学会这个，你不能光会抄模板就会区间修改和求个区间和，因为实际应用经常会使用它的变形，还是在于理解（理解后背板）。
数据结构 首先，回想一下heap的结构，它使用一个数组，同时使用下标本身来表达父子关系，这样的方式能节省大量指针所需要的内存空间，以下也使用这种表示方法来表示一棵线段树，也就是说，这里介绍的，属于狭义线段树。假设我们的数据是以下这样
下标 1 2 3 4 5 6 7 8 数据 1 0 5 2 3 4 0 1 构建线段树后结果如下
graph TD; 1,8:16-->1,4:8 1,8:16-->5,8:8 1,4:8-->1,2:1 1,4:8-->3,4:7 1,2:1-->1,1:1 1,2:1-->2,2:0 3,4:7-->3,3:5 3,4:7-->4,4:2 5,8:8-->5,6:7 5,8:8-->7,8:1 5,6:7-->5,5:3 5,6:7-->6,6:4 7,8:1-->7,7:0 7,8:1-->8,8:1
后缀数组其实概念很好理解，就是给出一个字符串，长度是n，对它所有的n个后缀编号从1到n进行排序，排序后，最小的那个后缀的编号假设是m1，那么sa[1] = m1，类似地，第二小的是m2的话，sa[2] = m2，sa这个数组就是我们所需要的后缀数组。根据这个，我们可以直接用sort算出sa，以下为最简单的实现
struct SA_simple { vector<int> sa; int s_size; const char* p_s; int size() const { return s_size; } static bool cmp(const char* x, const char* y) { return strcmp(x, y) < 0; } void init(char * str) { int n = strlen(str); s_size = n; p_s = str - 1; sa.resize(n + 1); vector< const char* > rp; rp.resize(n + 1); for (int i = 1; i <= n; ++i) { rp[i] = p_s + i; } sort(rp.begin() + 1, rp.end(), cmp); for (int i = 1; i <= n; ++i) { sa[i] = rp[i] - p_s; } } }; 这个实现的时间复杂度 $O(n^2logn)$
要注意的一点是下标从1开始。有了这个，可以做点什么呢？例如给你一个串p，求出p在主串s中出现了多少次。那么在有了sa的情况下，因为sa是有序的，问题就变成了二分搜索，分别用lower_bound和upper_bound通过sa搜索p，两个相减便得出现次数。