来自luogu的题解，学习了一下这个神奇的东西（其实只是看懂了期望复杂度证明和原理，然后抄了个模板而已。。。。
吐槽为啥LaTex复制都是重复的，害得我一点一点整理
柯多丽树
1. 珂朵莉树的原理
将序列拆成区间来暴力维护。
如: 1, 3, 3, 4, 7, 2, 2, 21,3,3,4,7,2,2,2
会被拆成(其中一种拆法)：
但也有可能会会被拆成(这也正是珂朵莉树会被卡的原因之一)：
2. 珂朵莉树的适用范围
题目数据随机且有区间修改操作(如本题)或者对拍(因为好打)以及骗分。
3. 珂朵莉树的节点
1 | template<typename _Tp> //要维护信息的类型 |
每个节点维护一段区间[l,r][l,r]及其上的值vv(注意区间不能相交)。(注：下面不再区分节点和区间，即区间有可能是节点，节点也有可能是区间，需结合自己理解。)
4. 珂朵莉树的构造
1 | template<typename _Tp> //要维护信息的类型 |
珂朵莉树继承了set,使得可以像使用set一样使用它，并重命名了一些冗长的数据类型，以及附加了两个新操作。
5. 珂朵莉树的操作
it split(int pos)
1
2
3
4
5
6
7
8template<typename _Tp>
typename chtholly_tree<_Tp>::it chtholly_tree<_Tp>::split(int pos)
{
it itl = this->lower_bound(node(pos, -1, value()));
if(itl != this->end() && itl->l == pos) return itl; --itl;
it itr = this->insert(node(pos, itl->r, itl->v)).first; itl->r = pos - 1;
return itr;
}作用：将pospos所在的区间[l,r][l,r]分成[l,pos-1][l,pos−1]和[pos,r][pos,r]并返回[pos,r][pos,r]所在的迭代器(若pos = lpos=l则返回[l,r][l,r]所在的迭代器)。
内容：首先 lower_bound(node(pos, -1, value()) 返回左端点大于等于pospos且最小的区间所在的迭代器并赋给迭代器itlitl，然后判断itlitl所指区间的左端点是否等于pospos，如果是的就直接返回itlitl即区间[l,r][l,r]所在的迭代器，否则就跳到上一个迭代器(即左端点小于pospos且最大的区间所在的迭代器)，接着 insert(node(pos, itl->r, itl->v)).first 会复制区间[l,r][l,r]上的[pos,r][pos,r]并插入且返回[pos,r][pos,r]所在的迭代器赋给itritr，此时只需将itlitl所指的区间[l,r][l,r]改为[l,pos-1][l,pos−1]即将rr改为pos-1pos−1即可，最后返回itritr即[pos,r][pos,r]所在的区间。
void assign(int l, int r, value x)
1
2
3
4
5
6template<typename _Tp>
void chtholly_tree<_Tp>::assign(int l, int r, value x)
{
it itl = this->split(l), itr = this->split(r + 1);
this->erase(itl, itr); this->insert(node(l, r, x));
}作用：将区间[l,r][l,r]上的序列所共有的值修改为xx。
内容：首先 split(l) 返回一个以ll为左端点的区间的迭代器赋给itlitl, split(r + 1) 返回一个以r + 1r+1为左端点的区间的迭代器赋给itritr, 然后 erase(itl, itr) 会删除所有左端点在区间[l,r + 1)[l,r+1)即[l,r][l,r]的区间即删除区间[l,r][l,r]上的整个序列， 接着 insert(node(l, r, x)) 会插入一个序列所共有的值为xx的区间[l,r][l,r]。
注意：请确保调用 split 和 assign 时 chtholly_tree 不为空。
6.珂朵莉树的声明
一维：
1 | //重命名 |
二维：
1 | //重命名 |
7. 珂朵莉树的初始化
1 | for(int i = 1; i <= n; i++) |
注：如果一开始序列是空的那么就 T.insert(l, r, v) 其中[l,r][l,r]为全域大小，vv为一个空值，如 T.insert(0, (int)1e9, 0) 。
8. 珂朵莉树的暴力维护
区间加
1
2
3
4
5
6//将[l,r]区间所有数加上x
void add(int l, int r, value x)
{
it itl = T.split(l), itr = T.split(r + 1);
for(; itl != itr; ++itl) itl->v += x;
}直接将左端点在[l,r)[l,r)的区间中最左边的区间依次加到最右边的区间。
区间修改
1
2
3//将[l,r]区间所有数改成x
void change(int l, int r, value x)
{ T.assign(l, r, x); }调用 assign 直接修改
区间第k小
1
2
3
4
5
6
7
8
9
10
11
12
13//将[l,r]区间从小到大排序后的第x个数是的多少
value select(int l, int r, value x)
{
it itl = T.split(l), itr = T.split(r + 1);
vector<pair<value, int> > vp;
for (; itl != itr; ++itl)
vp.push_back(pair<value,int>(itl->v, itl->r - itl->l + 1));
std::sort(vp.begin(), vp.end());
for(vector<pair<value,int> >::iterator it = vp.begin(); it != vp.end(); ++it)
if((x -= it->second) <= 0)
return it->first;
return -1;
}将左端点在[l,r)[l,r)的区间中最左边的区间到最右边的区间依次复制到 vector 里，排序，顺次找到第k小(注意：vector 里保存的是区间)。
区间幂次和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21//快速幂
value pow(value x, value y, value m)
{
value res = 1, ans = x % m;
while(y)
{
if(y & 1) res = res ans % m;
ans = ans ans % m;
y >>= 1;
}
return res;
}
//返回[l,r]区间每个数字的x次方的和模y的值
value sum(int l, int r, value x, value y)
{
it itl = T.split(l), itr = T.split(r + 1);
value res = 0;
for(; itl != itr; ++itl)
res = (res + (itl->r - itl->l + 1) pow(itl->v, x, y)) % y;
return res;
}将左端点在[l,r)[l,r)的区间中最左边的区间到最右边的区间依次快速幂累加即可。
9. 珂朵莉树的时间复杂度
记 mm为区间数即T.size()。
对于随机的ll和rr其区间[l,r][l,r]的平均长度为\frac{n-1}{3}3n−1
证明：$\overline{x} = \frac{\sum{l=1}^{n}\sum{r=l}^{n}(r-l)}{\sum{l=1}^{n}\sum{r=l}^{n}1}=\frac{\frac{1}{2}\sum{l=1}^{n}(\sum{l=1}^{n}l^2-(2n+1)\sum_{l=1}^{n}l+n^3+n^2)}{\frac{1}{2}n(n+1)} =\frac{\frac{2}{3}n(n+1)(n-1)}{\frac{1}{2}n(n+1)}=\frac{n-1}{3}$
m(平均值)的上界为$(log_\frac{3}{2}4)(log_2n)$
因为准确界我求不出来由于m与n对应，每次 assign 均会使得m变为$\frac{2}{3}m+\frac{2}{3}$且有概率在$l$及$r$上分裂出两个新区间，又因为只需求出$m$(平均值)的上界于是我们可以使得每次 assign 均会使得m变为$\frac{2}{3}m$，且永久地增加两个区间，可知进行k次操作后m变为$(\frac{2}{3})^km$有$1=(\frac{2}{3})^km$即$k=log\frac{3}{2}m$，于是最终会有$2k$即$2log\frac{3}{2}m$个区间，由初始条件$m=n$得出在进行足够多的 assign 情况下m(平均值)的上界为$2log\frac{3}{2}n$即$(log\frac{3}{2}4)(log_2n)$。(经过测试m的收敛速度远没有上述那么快($n=1e8$时大约要$1e6$次 assign 操作m(平均值)才会基本上不会变动)，另外m(平均值)的值大约在$\frac{3}{2}log_2n$左右)。
split 的均摊时间复杂度为$O(log_2log_2n)$
由 split 的时间复杂度为$O(log_2m)$可知 split 的均摊时间复杂度为$O(log_2log_2n)$。
assign 的均摊时间复杂度为$O(log_2log_2n)$
由 assign 的时间复杂度为$O(log_2m)$可知 assign 的均摊时间复杂度为$O(log_2log_2n)$
add 的均摊时间复杂度为$O(log_2n)$
由 add 的时间复杂度为$O(m)$可知 add 的均摊时间复杂度为$O(log_2n)$。
change 的均摊时间复杂度为$O(log_2log_2n)$
由 change 的时间复杂度为$O(log_2m)$可知 change 的均摊时间复杂度为$O(log_2log_2n)$
select 的均摊时间复杂度为$O((log_2n)(log_2log_2n))$
由 select 的时间复杂度为$O(mlog_2m)$可知 select 的均摊时间复杂度为$O((log_2n)(log_2log_2n))$
sum 的均摊时间复杂度为$O(log_2n)$
由 pow 的时间复杂度为$O(1)$(全域为[1,1e9][1,1e9])，及 sum 的时间复杂度为$O(m)$可知 sum 的均摊时间复杂度为$O(log_2n)$。
从此可以看出珂朵莉树的时间复杂度完全是由随机的 assign 操作保证的，这也就导致了珂朵莉树的适用范围狭小。
终于搞定了。。
然后愉快的打了个模板（谁叫我甚至不会STL的迭代器啊。。）
Code：
10.珂朵莉树的参考程序
1 |
|
再放一个傻题就可以继续愉快的理解SAM了！
[中山市选]杀人游戏
题目描述
一位冷血的杀手潜入Na-wiat，并假装成平民。警察希望能在NN个人里面，查出谁是杀手。警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人，谁是杀手，谁是平民。假如查证的对象是杀手，杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。
问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？
输入输出格式
输入格式：
第一行有两个整数 N,MN,M。 接下来有 MM 行，每行两个整数 x,yx,y，表示 xx 认识 yy（yy 不一定认识 xx ,例如President同志） 。
注：原文zz敏感内容已替换
输出格式：
仅包含一行一个实数，保留小数点后面 66 位，表示最大概率。
输入输出样例
输入样例#1：
1 | 5 4 |
输出样例#1：
1 | 0.800000 |
说明
警察只需要查证11。假如11是杀手，警察就会被杀。假如11不是杀手，他会告诉警察2,3,4,52,3,4,5谁是杀手。而11是杀手的概率是0.20.2，所以能知道谁是杀手但没被杀的概率是0.80.8。
对于100\%100%的数据有$1≤N≤100000,0≤M≤300000$
题解
有一定图论基础就不难想出本题，话说这道题我实现一开始各种挂，尽管想的完全正确（包括排除）
发现问题等价于询问有多少个入度为0的点。
又转念一想，如果有个人他其他人都确定了那他也确定了所以不用再询问一次。
因此加点判断就OK了。
Code：
1 |
|
SAM正式学习笔记
经过一番艰难重重的预习，我们大概知道了SAM的思想，各种引理以及一些相关性质。
那么现在让我们完完整整从入门到放弃精通
大量抄袭借鉴OI Wiki，竞赛入门经典（这本书在我理解SAM时起到了重要作用）。
引言：
首先我们需要明白什么是DFA（有限确定状态自动机）。
接下来我们会引入SAM最重要的概念：Endpos等价类，这是SAM与暴力之间的巨大差别。
我们还会学习后缀链接与后缀树（由Endpos通过后缀链接链接而成的）。
正式
明确一些概念：
后缀自动机的定义
给定字符串 的后缀自动机是一个接受所有字符串 的后缀的最小DFA（确定性有限自动机或确定性有限状态自动机）。
换句话说：
- 后缀自动机是一张有向无环图。顶点被称作状态，边被称作状态间的转移。
- 一个状态$t_0$为初始状态，它必定为这张图的源点（其它各点均与$t_0$联通）。
- 每个转移都标有一些字母。从一个顶点出发的所有转移均不同。
- 一个或多个状态为终止状态。如果我们从初始状态 出发，最终转移到了一个终止状态，则路径上的所有转移连接起来一定是字符串$w$的一个后缀。$w$的每个后缀均可用一条从$t_0$到一个终止状态的路径构成。
- 后缀自动机是所有满足上述条件的自动机中顶点数最少的一个
请认真阅读上面的每一句话，这将对你理解后面的Content至关重要。
子串的性质
后缀自动机最简单和最重要的性质是，它包含关于字符串$w$的所有子串的信息。任意从初始状态$t_0$开始的路径，如果我们将转移路径上的标号写下来，都会形成 的一个子串。反之每个$w$的子串对应于从$t_0$开始的某条路径。
为了简化表达，我们将会说子串对应于一条路径（从 开始且一些标号构成这个子串）。反过来我们说任意一条路径对应于它的标号构成的字符串。
一条或多条路径可以到达一个状态，因此我们说一个状态对应于字符串的集合，这也对应于那些路径。
看完这里也许你会奇怪这不是Trie吗，不过Trie的功能与时空复杂度在后面我们会看到比SAM差远了。
构造后缀自动机的实例
我们将会在这里展示一些简单的字符串的后缀自动机。
我们用蓝色表示初始状态，用绿色表示终止状态。
对于字符串 $s=” “$：
对于字符串$s=’a’$ ：
对于字符串 $s=’aa’$：
对于字符串 $s=’ab’$：
对于字符串$s=’abb’$ ：
对于字符串 $s=’abbb’$：
这里给出luogu上一个高手写的生成关于SAM图像的程序，您需要用graphviz打开生成文件
1 |
|
输入第一行n为串的个数，下面n行每行一个串
如果是普通SAM输入n=1输入一行，广义SAM输入n>1输入n行即可
使用方法：
1、先进入你生成test.dot文件的主目录下。
2、用cd进入子目录
3、运行 dot test.dot -T png -o test.png
在原目录下出现test.png就是SAM图像
假如这里你能看出构造的基本原理，那说明您很有天赋。
看不懂也没关系，让我们一步一步来。
请移步SAM正式学习笔记