学习知识点时遇到比较好的博客文章，记录一下。
然后这些文章里面又有对其作者启发的文章也建议看看。
我只是记录了我自己看了比较有启发的文章。
图论
匈牙利算法
数据结构
分块
数列分块总结——题目总版（hzwer分块九题及其他题目）（分块） - Flash_Hu - 博客园
【知识总结】分块和值域分块_Cutele_的博客-CSDN博客
分析主要分为两部分：不完整的块、整块、预处理/维护（又分为数据的性质，单个数据的标记，如排序，统计是否为0，元素和 ...）...
比如，统计大于/小于的个数，就可以采用维护排序的做法，然后维护时可以用各种各样的数据结构。
因为很多时候还是要保持有原来的序列，所以常常要另外为每一块开一个数组。
选取的块的大小，可能因为和数据有关，就比较玄学（bushi），具体调参，可以生成大数据，然后用两个设定不同的对拍，看运行时间。
带插入的，用重新分块的操作，既可以在一块过大，也可以在$\sqrt{n}$次插入后重新分块等。
有时候还需要把块区间预处理出一些数据，复杂度一般为$O(块多少 \cdot n)$。
多个标记需要想清楚更新的先后顺序。
这边也贴一下我的分块九题code好了。虽然第三题std有点锅，直接set.erase掉，它这一个数就全删了，但还是orz hzwer学长。
后几篇是讲区间众数、值域分块、莫队相关，也是由hzwer学长的第九题引出的。
Kruskal重构树
学习笔记：Kruscal 重构树 - DMoRanSky - 博客园
图很棒，看图就很容易理解了。
（现在的理解）是用来求两个点之间经过的最大/最小路径的最小/最大值，转化为两点的LCA。
以求最大值的最小值为例，整个重构的过程，可以想我们的目标是把答案放在LCA，那么就是从小到大枚举边权，然后小的先合并，之后都用DSU的祖先来整体来看，也就是想要跨越这两个集合，一定要经过新加进来的边（因为比他小的边连完后，这两个集合仍然独立）。
重构树更多是一种思想，比如Problem - F - Codeforces就是重构树，思路类似于Kruskal重构树，但是可以不把另外的点建出来。
杂
浅谈 OI 中的数据结构题 - DPairの博客 - 洛谷博客
二维数点
思想来自扫描线（在本文计算几何章节）。
大概是枚举一维（扫描一维），然后数据结构弄另一维。
一般是离线的，在线加可持久化可以解决（我还没写过）。
珂朵莉树/老司机树（ODT）
珂朵莉树模板CF896C Willem, Chtholly and Seniorious题解 - 泥土笨笨
随机数据条件下，时间复杂度十分的香啊。
就是暴力啦。
动态规划
高维前缀和/子集和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
生成函数
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
该文章已经关闭评论