学习知识点时遇到比较好的博客文章，记录一下。
然后这些文章里面又有对其作者启发的文章也建议看看。
我只是记录了我自己看了比较有启发的文章。
图论
匈牙利算法
匈牙利算法相关证明：为什么不需要考虑原有点的匹配方式；为什么只需要遍历一遍左部点；为什么回溯时 vis 数组不置零_smallC233的博客-CSDN博客
一些可能存在的疑惑，在这篇博客获得解决。
数据结构
分块
数列分块总结——题目总版（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の博客 - 洛谷博客
动态规划
高维前缀和/子集和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是通俗易懂的复杂度估计。
数学
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 - 转角法思维
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 - 博客园
开始的几篇文章哪一篇好像都可以一篇全吃（
莫队是对询问优化，尽量运用给前一次提问的信息来更新下一次提问的答案。
让左右双指针走的“步数”尽量相近。
容斥
虽然思想很简单，但是很多时候就忘了。
常伴随正难则反的想法。
Comments | NOTHING
该文章已经关闭评论