学习知识点时遇到比较好的博客文章，记录一下。
然后这些文章里面又有对其作者启发的文章也建议看看。
我只是记录了我自己看了比较有启发的文章。
Library Checker - 验板子的地方（大概）
[toc]
图论
图的匹配
从匈牙利算法到带权带花树——详解对偶问题在图匹配上的应用 | Potassium's blog
【学习笔记】一般图最大匹配(带花树) | 𝓞𝓻𝓬𝓱𝓲𝓭𝓪𝓷𝔂'𝔀 𝓫𝓵𝓸𝓰
【学习小记】一般图最大匹配——带花树算法 - BAJim_H - 博客园
Tutorial Blossom Algorithm for General Matching in O(n^3) - Codeforces
有些地方直接看文字说明不好理解，可能结合代码会通畅一点。
网络流
费用流
基于 Capacity Scaling 的弱多项式复杂度最小费用流算法 - ouuan
最大权闭合子图
问题：对于所有边 (u, v)，点 u 在子图中则 点v 必在子图中，求子图的点权和最大值。
$$ &w_i > 0 &\Rightarrow &add(S, i, w_i) \\ &w_i < 0 &\Rightarrow &add(i, T, -w_i) \\ &原图边(u, v) &\Rightarrow &add(u, v, INF) $$
闭合子图和 $S$ 构成 集合 $V_S$，其余点和 $T$ 构成 集合 $V_T$。
最大权闭合子图的权 $W = \sum_{i \in V_S} w_i[w_i>0] - \sum_{i \in V_S} \abs{w_i}[w_i<0]$；
最小割一定是简单割，最小割的值为 $c(S, T) = \sum_{i \in V_T} w_i[w_i>0] + \sum_{i \in V_S} \abs{w_i}[w_i<0]$；
则点权和最大值 $W = \sum w_i[w_i>0] - c(S, T)$，即正权点之和 - 最小割。
不要被限制关系迷惑了，如vjudge - 植物大战僵尸，限制关系，其实反过来考虑就是闭合子图。
直接上这种建图方式即可。注意排除一些题中一些性质不合法的情况，如上题就不能有环或被环连出的边。
总是转化为选 a 必须选 b 的形式，如vjudge - 寿司餐厅，题意就很麻烦，但可以转化来着，还需要熟练的连边方式和算边数的能力。
2-SAT
2-SAT速成 - 自为风月马前卒 - 博客园 (cnblogs.com)
2-SAT 的图具有对称性。
优化连边
线段树优化连边
把出点和入点放在线段树上，线段树内为了实现正常的点边关系（指到了这个点就可以从这个点出发等等）边权为 0，把要加的边加进去，区间到区间的，如果不加虚拟点，复杂度为 $O(log^{2}n)$，加了之后为 $O(logn)$。
出树从子节点向父节点连边，入树从父节点向子节点连边，共享（在线段树的叶子节点下面连原始点）。
原始点从出树出去，从入树回来；整体就是一个“回流”的过程。
原图上的边，连到虚拟点。（入边/出边加权或选择最后答案除二）
按照需求看需要建几棵线段树。
树上优化建边
树链剖分
配合线段树，和上方思想一致，按照需求看要建一棵还是两棵线段树。
注意在线段树里的下标代表树链剖分内部的 dfn。
一般建法需要 $log^2n$ 条边。
「BZOJ 4699」树上的最短路（最短路 + 树链剖分 + 线段树） | blunt_axe
使用重链的前缀优化可以只建 $logn$ 条边，原理是往上跳的过程中只有最后一段可能跳的不是重链的前缀。
具体前缀优化建边方式为：
对于每一个点，我们拆出一个虚点，原点向虚点连长度为 0 的边，然后每个虚点向下一个虚点连长度为 0 的边。这样在前缀对应的最后一个点向外连边就等价于在原图上对于前缀上的所有点连出一条边了。
倍增
倍增的同时，连边。和线段树类似的很容易在倍增数组上，连出这样的内部/外部边。
生成树
Kruskal, Prim
Boruvka
每一轮每个连通块独立去寻找到另一个连通块的最短边，选择这条边，如此迭代至多 $\log n$ 轮。
最短的边可能会是同一条边，所以并不会成环；且最坏情况下，两两配对，就是 $\log n$ 次。
因为相邻最近的异或和是小的，所以可以直接从深到浅去合并，只利用 Boruvka 的思想。
或者模拟各个连通块找最短边的过程。前者实现可以看 orzdevinwang 后者实现可以看 Qingyu 的。
还有直接分治的，jiangly 。
数据结构
分块
数列分块总结——题目总版（hzwer分块九题及其他题目）（分块） - Flash_Hu - 博客园
【知识总结】分块和值域分块_Cutele_的博客-CSDN博客
分析主要分为两部分：不完整的块、整块、预处理/维护（又分为数据的性质，单个数据的标记，如排序，统计是否为0，元素和 ...）...
比如，统计大于/小于的个数，就可以采用维护排序的做法，然后维护时可以用各种各样的数据结构。
因为很多时候还是要保持有原来的序列，所以常常要另外为每一块开一个数组。
选取的块的大小，可能因为和数据有关，就比较玄学（bushi），具体调参，可以生成大数据，然后用两个设定不同的对拍，看运行时间。
带插入的，用重新分块的操作，既可以在一块过大，也可以在$\sqrt{n}$次插入后重新分块等。
有时候还需要把块区间预处理出一些数据，复杂度一般为$O(块多少 \cdot n)$。
多个标记需要想清楚更新的先后顺序。
这边也贴一下我的分块九题code好了。虽然第三题std有点锅，直接set.erase掉，它这一个数就全删了，但还是orz hzwer学长。
后几篇是讲区间众数、值域分块、莫队相关，也是由hzwer学长的第九题引出的。
线段树
线段树分治
线段树分治总结（线段树分治，线段树，并查集，树的dfn序，二分图染色） - Flash_Hu - 博客园
第一篇文章是线段树分治和并查集的结合，其实还可以和很多其他做结合。
第一篇文章里面给的第二道题目不用维护高度也行，可能不开 $O_2$ 的情况不好过（？），总之可以不这么在意。
大致思路就是把不好做的删除操作用栈存下来撤回。
由于本质是跑了一遍 dfs 序，所以甚至可以不用显式的建出线段树。
吉如一（吉司机）线段树（seg-beats）
《区间最值操作与历史最值问题》 - 学习笔记 - p_b_p_b
线段树通过维护一些信息达成维护区间最值操作和历史最值的性质。
把区间最值操作转成区间加减貌似是写起来更好写（？）。
复杂度证明思想用到势能，可能也可以归于势能线段树（？）。
势能线段树，还有与，开根等等，只修改区间势能不为零的区间，一次修改的复杂度大多为$O(logn)$或$O(log^2n)$。
具体可以势能分析法证。下面有些题目。
李超线段树
选这篇主要是码风结构和我的写法比较像，参照的写比较容易。
Kruskal重构树
学习笔记：Kruscal 重构树 - DMoRanSky - 博客园
图很棒，看图就很容易理解了。
（现在的理解）是用来求两个点之间经过的最大/最小路径的最小/最大值，转化为两点的LCA。
以求最大值的最小值为例，整个重构的过程，可以想我们的目标是把答案放在LCA，那么就是从小到大枚举边权，然后小的先合并，之后都用DSU的祖先来整体来看，也就是想要跨越这两个集合，一定要经过新加进来的边（因为比他小的边连完后，这两个集合仍然独立）。
重构树更多是一种思想，比如Problem - F - Codeforces就是重构树，思路类似于Kruskal重构树，但是可以不把另外的点建出来。
杂
浅谈 OI 中的数据结构题 - DPairの博客 - 洛谷博客
二维数点 / 二维偏序
思想来自扫描线（在本文计算几何章节）。
大概是枚举一维（扫描一维），然后数据结构弄另一维。
一般是离线的，在线加可持久化可以解决（我还没写过）。
upd:
偏序算在点的左下角区域的点是好做的，只要一维排序，另一维数据结构，然后查询比要求的点低的点数就行。
求矩阵的话，需要离线下来，把查询拆成几部分（两部分一般），然后加加减减。
珂朵莉树/老司机树（ODT）
珂朵莉树模板CF896C Willem, Chtholly and Seniorious题解 - 泥土笨笨
随机数据条件下，时间复杂度十分的香啊。
就是暴力啦。
字符串
周期可以非完整，循环节是完整的。
求周期 等价于 求 border，s[i] =s[i+|s|-|p|]，就是周期。
border 不具有二分性。（不同的题目，Border 是否包含自己不一定）
Base > |字符数|
最好：Mod >= Base^2
周期定理：若 p, q 均为 S 的周期，则 (p, q) (gcd) 也为 S 的周期。
一个串的 border 数量为 O(N) 个，但他们组成 O(logN) 个等差数列。
置换意义下本质不同，采取映射后还是不同。
哈希
// 列点好用的哈希模数（1031252627
Trie 树
删除，先找到，然后递归往回删，到有别的点也要用的地方停，删终止标记。
（或者用持久化，即减小 cnt 的方式删掉，实现上更方便）
本质可以和字典序大小联系。
区间异或和最大 -> Trie树上前缀异或和。
数组大小应为，点数 × 层数（长度），然后第二维是看可能的分支数量。
查询和插入的函数参数，可以加上 root 和 dep，且查询的时候，建议把值过程中计累计 (1<<i) 算。这样可以方便在分治或者别的情况下，不重新建一棵 trie 树。
可持久化
持久化 01-Trie，可持久化维护 cnt[u] （在 u 的子树中的终止节点个数，判断节点是否真实存在）。
Border 树 （next 树，失配树，KMP 自动机）
求 next 数组，i 向 next[i] 连边，构成 n+1 个节点的树。
性质：
- 每个前缀 Prefix[i] 的所有 Border： i 节点到根的链。
- 有哪些前缀有长度为 x 的 Border： x 的子树。
- 求两个前缀的公共 Border： 求 LCA。
AC 自动机（ACAM）
给出一个字典，询问有多少字典串在询问串中出现过，即单串和多串的匹配问题。
AM 自动机 = Trie（前缀信息） + KMP（后缀信息fail链）， 是离线型数据结构，不支持增量添加字符串。
用于字符串询问类的离线处理，和 DP 结合或补成 Trie 图。
复杂度线性（Trie 字符串总长度×字符集大小 + fail O(n)），势能总量为 Trie 节点数总数。
建 Trie 树，BFS 遍历，到一个点，看它父节点的 fail 链，依次看 fail 链的点指向的子节点，有没有等于当前节点的值，有就指向那个等于当前节点值的点。（原始不带优化的AC自动机版本）
几个常数优化：
fail 优化
// 减少跳 fail // 在 build 时，从暴力跳 fail 找，变为 O(1) 赋值 fail[v] = tr[fail[u]][z] // z 为下一个字母Trie 图优化
// 减少跳 fail，考虑到跳完 fail 是为了继续扩展的情况 // 从没有对应子节点，跳 fail 去寻找下一个节点，到直接连接对应的节点 // 从 Trie 树变成了 Trie 图 // 省去了跳 Fail 链的复杂度 和 转移枚举字符集的复杂度，理论上最多优化 Trie深度*|字符集|。 tr[u][z] = tr[fail[u]][z]; // z 为下一个字母；在没有对应子节点时last 优化
// 减少跳 fail，用于（暴力）计数处理，从跳 fail 改为跳 last ，但实际上直接在 fail 树（记下入度就行）上bfs求和是不是就已经准确 O(n) 了 // 感觉不是很有必要。黏一下别人的代码 // build 时 last[c]=end[fail[c]]?fail[c]:last[fail[c]]; // 匹配时 void count(int x) { while(x) { //计数、打印等，视题目要求顶 x = last[x]; } } void match() { int now = 1; for(int i=1;s[i]!='\0';++i) { int x = s[i]-'a'; now = ch[now][x]; if(end[now]) count(now); else if(last[now]) count(last[now]); } }
计数看情况，大部分就建 fail 树上拓扑排序求就行 O(mn) ，有时 DFS 序 + 树状数组 在 fail 树上动态差分，利用在点到根节点上的点一定还有没有被回溯，当前点 +1，当前点被回溯后 -1 维护点到根的终止节点的个数 O(nlogn + mlogn) 如 string 。
计数是记所有到达的点，所在 fail 链的总和。
回文串
回文中心：奇数长度在中间，偶数长度是中间空的位置。
回文半径 L：回文中心到两边的距离，包括回文中心。
回文前（后）缀：是回文的前（后）缀。
常用 <回文中心，回文半径> 表示回文子串。
长度与半径的关系：|S\_奇| = 2L - 1, |S\_偶| = 2L
回文半径有可二分性。
回文串和 Border：对于_"回文串 S"_ ，回文前（后）缀等价于 Border。
哈希 + 二分
比较容易撞（？），因为检测次数为 nlogn 次。
Manacher（马拉车）
预处理： $S^\# = \#a\#b\#c\#$
所有回文串变成奇数长度的，极长的回文串的首尾必然都是 # 。
用法：
- 每个回文中心的回文半径；
- 求本质不同的回文串。新的回文串一定出现在使最右串移动的时候，因此至多有 N 个，把可能的进行去重就得到了所有本质不同的回文串。
PAM (回文自动机，EER TREE, PT 回文树)
结构类似于 ACAM，但是 PAM 是在线的数据结构。
节点至多有 N 个（由前面本质不同的回文串至多有 N 个可得），每个节点代表一种回文串。
S(u) 表示节点 u 代表的回文串，len[u] = |S(u)|。
后继边，每个后继边上有一个字母。用 trans(u, ch) = v 表示 u 有后继边 ch 指向 v 节点。则有 S(v) = chS(u)ch，len[v] = len[u] +2。
失配边，每个节点都有一个失配边，用 fail[u] = v 表示 u 节点的失配边指向了 v 节点。则有 S(v) 是 S(u) 的最大 Border，即最长回文后缀。
PAM 的构造，找每个前缀的回文后缀。
特殊：对奇偶回文串需要有两个根节点，长度加 2，所以，奇根长度为 -1，偶数长度为 0。
方便起见，奇(1, -1)偶(0, 0)根的 fail 互相指。（编号，长度）
跑两次 fail，一次确定 S[1, i] 产生的最大回文后缀，一次确定这个回文后缀的 fail。
和 ACAM 一样的时间复杂度分析 $O(2n)$，为线性后继边至多 N 条，朴素数组存边 (u, ch) -> v 空间复杂度为 $|S|\cdot |\Sigma|$ （字符串长度，字符集），只有 n 要存，但要开 26n。
被卡空间了的话：1. map、手写线段树存边，会带来额外的时空复杂度； 2. hash 存边，期望 O(1) 访问。
卡常好写小技巧：节点编号从大到小就是这棵 fail 树的拓扑序。
for i = tot ... 2
cnt[fail[i]] += cnt[i];
cnt[0] = cnt[1] = 0;注意：
上次节点加进去的位置是 last，而不是 tot！
Palindrome Series
用于解决枚举回文后缀的 DP：
$f[i] = \max \{ cost[p] + f[i-p-1] \} ， p 是回文后缀$ cost[p] 回文串的花费，S 分割成若干回文串。
需要枚举所有回文后缀。暴力 $O(n^2)$ 。
回文串的回文后缀是 Border，而 Border 是有良好的等差数列性质，最多有 log 个等差数列，类似于 fail 树上按等差数列进行剖分，一段一段，从前往后枚举的时候，维护这 logn 段的前缀和或者别的信息，变为 $O(nlogn)$。
后缀数组
后缀排序：把所有后缀按字典序升序排序。
后缀排名 rk[i] ：rk[i] 表示后缀 S[i] 在后缀排序中的排名，即它是第几小的后缀。
后缀数组 sa[i] ：sa[i] 表示排名第 i 小的后缀。
rk[sa[i]] = i
sort 字符串的复杂度是 $O(\Sigma|s_i| \cdot logn)$
SA
求后缀数组：
naive sort 法 $O(n\log^2n)$
二分 + Hash，写比较函数，hash 检测次数 $n\log^2n$ 次，容易冲突。在一些奇怪字典序的时候可能要用。
前缀倍增法 $O(n\log n)$
定义 $S(i, k) = S[i, i+2^k-1]$，i 开始，长度为 $2^k$ 的子串。
后缀大小关系比较价于 $S(i, \infin), S(j, \infin)$ 的字典序关系。
所以只需要将 $S(i, \lceil\log_2n\rceil)$ 排序。
假如有了 $S(i, k)$ 的排序结果，即 $rk[S(i, k)], sa[S(i, k)]$ ，看着两位数基数排序，就可以排序 $S(i, k+1)$。
基数排序常数 5~6。
DC3, Difference Cover-3 $O(n)$
将所有后缀按照下标 mod 3 分类，后缀1、后缀2、后缀0.
整体过程：先把后缀1、后缀2排序，后缀0排序，再归并。
显然 S[1] 和 S[2] 包含同模数下标的所有后缀。（这里 S[i] 都指从 i 开始的后缀）
先把 S[1]、S[2] 补成 3 的倍数，若已经是了，那就补 3 个。
再前后拼接处理后的 S[1] 和 S[2]，记为 T，此时问题转化为排序 T 所以 mod 3 = 1的位置后缀。
每 3 个位置打包看成一个三位数，进行基数排序。
规模变为 $\frac{2n}{3}$ ，后面等价于对 T' (rk) 继续求后缀数组。
排序后缀0时，利用前面求出来的后缀1的排名，S[3k, n] = S[3k] + S[3k+1, n]，看作两位数的基数排序。
后缀12与后缀0归并。
比较后缀0和后缀1大小：S[3k, n] = S[3k] + S[3k+1, n], S[3p+1, n] = S[3p+1] + S[3p+2, n]，后一位相对顺序已知，看作两位数 $O(1)$ 。
比较后缀0和后缀2大小：同理拆成三位数 $O(1)$ 比较。
递归复杂度 $T(n) = T(\frac{2n}{3}) + O(n), O(n + \frac{2}{3}n + (\frac{2}{3})^2n + \cdots) = O(\frac{n}{1-\frac{2}{3}}) = O(3n)$
再算上基数排序复杂度，常数接近 20，实际表现只比倍增好一点。
SA-IS $O(n)$
小常数，大概基数排序的常数。
后缀数组性质：
LCP的性质
有一组排序过的字符串，如何快速求他们的LCP？
结论：“区间可加性“：$\forall k\in \lbrack i, j\rbrack, LCP(A_i, A_j) = LCP(LCP(A_i, A_k), LCP(A_k, A_j)) = min(LCP(A_i, A_k), LCP(A_k, A_j))$
证明： 分类 $LCP(A_i, A_k)$ 是否等于 $LCP(A_k, A_j)$ 来证明。
Height[i] = LCP(s[i, n], S[sa[rk[i]-1], n])，即后缀i和排名比它小一的后缀的LCP。
结论：$Height[i] \ge Height[i-1] - 1$
证明：分类 $Height[i-1] \le 1, Height[i-1] > 1$，第一种显然，第二种删第一个字符，利用LCP的“区间可加性”转变为有 Height[i]。
势能分析复杂度，$O(n)$。
实际使用时，常常使用 $H[i] = Height[sa[i]] \iff H[rk[i]] = Height[i]$ 表示排名为 i 与 i-1 的LCP，即 $H[i] = LCP(S[sa[i], n], S[sa[i-1], n])$.
Height 数组的应用
求本质不同子串
$Ans = \sum n - sa[i] + 1 - H[i]$
两子串最长公共前缀
$LCP(sa[i], sa[j]) = \min\{H[i+1..j]\}, i和j为排名$
两个不同串的公共子串相关
先用特殊字符连接两个串，后缀排序，得到 H 数组。（特殊字符一般会选 'a'-t, 'z'+t，保证字典序还可以用）
选的时候，注意要分开选择在两个串内的后缀，不要选成一个串的两个后缀了。
$\max(0, \min(H[l..r])-K)$ , 长度大于 K 的的个数，具体求这个东西就各种数据结构、分治来搞了。
...
SAM（后缀自动机，DAWG，单词的有向无环图）
S的后缀自动机是能识别所有 S 的子串的自动机类型的数据结构（确定有限自动机，DFA）。
自动机 = 状态集合(state) + 状态转移(trans) + 起始状态 + 终止状态 + 字符集。
naive 后缀自动机
把 S 的所有后缀依次插入到 Trie 里，状态数、转移数都是 $O(n^2)
最简状态后缀自动机
s(w) 子串 w 对应的后缀自动机上的状态。
trans(s, ch) 当前状态为 s，接受新字符 ch 之后到达的状态。
Trans(s, str) 当前状态为 s，接受新字符串 str 后到达的状态。
Suf(i) 从 i 位置开始的后缀。
$Right(s) = {r_i}$ 表示 s 状态代表子串的出现位置的右端点。
所有节点的 Right 集合不完全相同。
SC(suffix-chain) 树（后缀链接树）（Parent 树、link 树）
性质
每个前缀所在状态两两不同。
树上共有 |S| 个叶子节点，分别对应每个前缀所在状态。
树至多有 2|S|-1 个节点，即至多有这么多不同的 Right 集合，节点数 $O(2n)$。
任意串 w 的或追全部位于 s(w) 的后缀链接路径上。
若某状态 s 有 ch 转移边，那么它的父节点 f(s) 一定有 ch 的转移边。（但不一定转移到同一个状态）
每个状态 s 的 Right(s) 等价于后缀链接树上子树的叶子的集合。
观察
$MaxL[f(s)] = MinL[s] - 1$ ，因此每个点只需要记 MaxL。状态 s 表示的长度为 ( L[f(s)], L[s] ] 的串。
终止状态代表至少一个后缀。（不能往后转移了）
Right 集合概念等价于子树概念，不用再具体维护，只需要维护树。
状态数：根据 DFA 的性质，到后缀的路径是唯一的，所以非树边到达经过的最多一条，所以 $O(3n)$ 。
在线增量构造
第一个节点，标号为 1 表示 root （空字串），L[1] = 0，f(1) = 0(null)，且 R(1) 为全集。
从 S[1, i-1] 到 S[1, i]，新增了 i 个子串（S[1, i]的所有后缀串）
（last 是上一个版本的 np）新建节点 np，trans[np]清空，L[np] = L[p]+1, last = np
p 到 p'，没找到 p'，f(np) = root；
找到了 p'，如果 L(q) = L(p') + 1，f(np) = q；
如果 L(q) != L(p') + 1，建 nq，trans(nq) = trans(q), f(q) <- nq <- q
找到 p* 不指向 q，指向 nq，f(np) = nq。
Right 集合的树，有时需要显式建出来，有时构出拓扑序也就可以了。
应用
求最小循环串
...
动态规划
常见模型（？）
子序列 -> 线性
高维前缀和/子集和DP (SOS DP, sum over subset)
SOS Dynamic Programming Codeforces
Tutorial on Zeta Transform, Mobius Transform and Subset Sum Convolution - Codeforces
这部分好像思想与FMT/FWT比较类似，那边的文章也可以看看。
多维独立的信息，分步再整合的感觉。
树上背包
子树合并背包类型的dp的复杂度证明_背包型树形dp 复杂度_cervoliu的博客-CSDN博客
LCA是通俗易懂的复杂度估计。
数学
线性基
与线代相关，但知道基底也就比较好理解， 来求子集最大异或和等问题，分为贪心和高斯消元两种求法，oi-wiki上说高斯消元法有的，贪心法没有的性质，可以在贪心的求完后，用比自己低位的消掉1获得一样的效果。感觉merci大佬的写法很好qwq（当然也可以先插入然后再统一消除）
FFT/NTT
FFT/NTT 多项式学习笔记 - Fenghr - 博客园
NTT&FFT 快速？变换,以及扩展 - chasedeath - 博客园
因为系数表达式相乘不方便，而点值表达式相乘，直接点值的函数值相乘就行，所以用FFT把系数表达式转化为点值表达式，相乘后，再用IFFT（FFT的逆操作）变回系数表达式。推导看下来大概就会明白FFT和IFFT的联系，然后复数运算常数比较大，自己实现下这个类比较好。
FMT/FWT
位运算卷积(FWT) & 集合幂级数 - command_block 的博客 - 洛谷博客 (luogu.com.cn)
快速沃尔什变换/FWT 详详详解_Hypoc_的博客-CSDN博客
快速变换之Fast Mobius Transform - 知乎
快速莫比乌斯变换 / Fast Mobius Transform, FMT - AE酱 - 博客园
快速沃尔什变换及快速莫比乌斯变换学习笔记 | Bill Yang's Blog
博弈论
二分图博弈模型
【蒟蒻数学】巧妙运用二分图解决博弈论 - 蒟蒻のBLOG (jvruo.com)
树上博弈
生成函数
Tutorial] Generating Functions in Competitive Programming - Part 1 - Codeforces
Tutorial] Generating Functions in Competitive Programming - Part 2 - Codeforces
计算几何
点在多边形内部
一般多边形是O(n)，凸多边形可以二分logn
做法上，除了确定是凸多边形且有按照一定顺序排列的是可以logn确定是否在区域内，
一般的多边形，如果是普通多边形，射线法和转角法一致，而非一般的复杂多边形，两者对多边形区域的判定是有区别的。
如GIS算法基础（二）计算几何基础（中） - 小钟233 - 博客园中提到的例子（我做对横坐标和纵坐标都做了-3的偏移。
Input:
7
0 6
6 0
15 15
9 15
18 0
24 6
12 27
1
12 12
Output:
OUT - 射线法
IN - 转角法扫描线
【学习笔记】扫描线 - NCC-79601 Captain's Log - 洛谷博客
扫描过程通过OI Wiki来看。
面积的并，第二篇博客讲得很详细。用线段树维护当前高度被覆盖的区间的总长度与当前区间被覆盖的次数。由于是独立的矩形且是覆盖关系，所以每个区间的信息是独立的，所以不需要在小区间修改的时候，不需要把父区间的信息pushDown。
周长的并，第三篇博客分析得很清楚，第二篇较简略。
第一种是横向、纵向分别求。此时，每次操作对高度的贡献就是操作前状态和操作后状态的长度改变量，此时涉及同一高度的线段要先加后减的问题，因为我们用绝对值取改变量，如果每次操作后就加上此操作的贡献，会导致加上不存在的线段两倍，在排序的时候先加即可避免出现不存在的空缺；或者，同一高度的线段全都操作完，再计算当前高度的总贡献应该就没有这个问题，但是实现上显然没有上面直接求方便。
第二种，在一个方向上和第一种的其中一次一样。一个方向的解决了。我们考虑另一个方向的（假定是纵向的），首先是每一根的长度，显然是两次操作的高度差；那么有多少个这样的长度呢？想到这样的线是从低到高连过来的（假定从低到高操作），那么就当前高度的独立段数*2，每一段都是从下面的两根线段围起来的。最终就有这两篇博客中的结果。
求凸包
数论小白都能看懂的平面凸包详解 - ShineEternal的笔记小屋 - 洛谷博客
思维
Meet in the Middle
Meet in the middle算法总结 - birchtree - 博客园
之前学过双向广搜，其实就是这个思想。
若为 闭区间
dfs(0, n/2-1, 0, ans1);
dfs(n/2, n-1, 0, ans2);
/**********或者************/
dfs(1, n/2, 0, ans1);
dfs(n/2+1, n, 0, ans2);
/* 不然会造成RE/MLE等情况，因为不是一半分
就记忆下面的这种就行，上面是都-1。 */DSU On Tree
Tutorial Sack/dsu on tree - Codeforces
主要是启发式合并的思想，这几篇文章提到的基本上还是轻重链的形式。Problem - E - Codeforces，这一题也是启发式合并，但不是轻重链，而是把要维护的信息用map来维护，合并的时候是启发式合并的思想。所以，主要是启发式合并的思想。
这种形式，我的理解是：
对每个子树来说，是对大的部分（重儿子）保留，轻儿子暴力求，有点把轻儿子合到重儿子的意味。然后，对于当前子树是重儿子的链，在后面被当作轻儿子时，一样要清空暴力求，来保证结果的正确性。从单个子树来看，它每棵子树都是从轻儿子开始求，然后撤除轻儿子的答案，来避免影响之后求重儿子，而重儿子因为是最后一个求，就保留只跑一遍，可以传递回父节点的值。
关于时间复杂度第二篇文章比较清楚，就不再反复论证了。
莫队
莫队算法——从入门到黑题 - WAMonster - 博客园
莫队细讲——从零开始学莫队 - Hastieyua - 博客园
开始的几篇文章哪一篇好像都可以一篇全吃（
莫队是对询问优化，尽量运用给前一次提问的信息来更新下一次提问的答案。
让左右双指针走的“步数”尽量相近。
容斥
虽然思想很简单，但是很多时候就忘了。
常伴随正难则反的想法。
cdq分治
CDQ分治总结（CDQ，树状数组，归并排序） - Flash_Hu - 博客园
三维信息，模板题的非严格比较需要去重。
第一维，现在外部排序，需要在cdq分治内的归并过程中满足两段性质；
第二维是在归并过程中排序；
第三维一般是用数据结构（常常是树状数组/线段树）维护并查询。
Comments | NOTHING
该文章已经关闭评论