【模板】并查集及几种变化

并查集(Union-Find Set，个人常写作UnionSet)，就是可以合并，可以查询的集合。朴素并查集是最简单的数据结构之一。

【模板】后缀数组SA-IS

常见的后缀数组求法为 $\rm O(nlogn)$ 的倍增求法，也有DC3或后缀自动机 $\rm O(n)$ 构造的。我们今天要讲的也是一种 $\rm O(n)$ 构造后缀数组的算法，SA-IS(SuffixArray-InducedSort)。

替罪羊树(SGT)，又叫重量平衡树，通过将不平衡的子树拍扁重构来保证整棵树的平衡。

FFT~~(forever fast TLE)~~是个很神奇的东西，可以用 $\rm O(nlogn)$ 的时间复杂度来解决多项式乘法的问题（朴素为 $\rm O(n^{2})$ 。

选了个很简陋的主题

很多东西都要我自己魔改开发

当时现场A了这道题，成功以非正式的身份吓到了正式选手。后来听讲解发现好像和我的思路不太一样，所以发一下我的做法

给定一个长度为 n 的序列 a，一共有 m 次操作，
每次操作给定 x, y，使序列中所有 x 变成 y，问每次操作后，值相等的位置的最小下标差是多少。若序列中无相同的数，则输出2147483647。

n, m <= 1e5, 所有数在int范围内

给定指定的一个有向图，其中有两个特殊的点源S(Sources)和汇T(Sinks)，每条边有指定的容量(Capacity)，求满足条件的从S到T的最大流(MaxFlow)。

2018-04-08 已更新

很久以前就想写博客来记录OI生活中各种各样的事了

每次看到各种dalao们的博客总希望能有一个属于自己的博客

于是在2018年3月25号，从长春回来的第二天，在各位dalao的帮助下，我创建了自己的博客