简述
线性基应该算是线性代数范畴内的东西。在 OI 中，线性基被用来解决位运算或者是向量表示的问题。
建议读者学习了高中数学中的向量之后再来阅读本文，相信这样会帮助理解线性基。
P3313:「SDOI2014」旅行题解
P4899:「IOI2018」 werewolf 狼人题解
解法
这道题是 Kruskal 重构树的裸题。我们先来考虑从\(s\)出发的人形状态，我们要找到一个点点权小于\(L\)的点，就相当于在 Kruskal 重构树上倍增找到最后一个小于\(L\)的点。我们把符合人形规律的 Krukskal 树记为 Tl，其中构造它的方式就是把原来图上所有边的边权赋值为端点的最大值，然后按最小生成树的方式去构造重构树；符合狼形规律的 Kruskal 重构树被记为 Tu，其中构造它的方式就是将端点编号最小值赋为边权，然后按最大生成树的方式构造。之后，我们再到主席树中求交集即可，如果有交集那么查询结果为一个不为零的数，输出\(1\)即可；没有交集那么查询结果即为\(0\)，输出\(0\)。
主席树总结
简述
主席树是一个很有意思的数据结构，其全称其实是「可持久化线段树」，至于为什么叫「主席树」是因为：
由于发明者黄嘉泰姓名的缩写与前中共中央总书记、国家主席胡锦涛（H.J.T.）相同，因此这种数据结构也可被称为总书记树或主席树。
From Wikipedia.org
Kruskal 重构树
简述
Kruskal 重构树是图的一种生成树，主要解决一类路径边权限制问题。Kruskal 重构树有按深度单调的性质，所以很容易就可以解决边权的取值限制。
建法
Kruskal 重构树的建造方法和 Kruskal 算法建最小生成树的方法非常类似，但是结构有所不同：Kruskal 重构树将边权变成点权，点权依深度变小。我们假设有一张这样的图：
P3980:「NOI2008」志愿者招募题解
解法
我们可以把整个工作流程想像成网络流上的一条链：第\(i\)天连接到第\(i+1\)天的，流量为\(INF – A_i\)，费用为\(0\)；其中第\(n+1\)连接到汇点，流量为\(INF\)，费用为\(0\)；源点连接到点\(1\)，流量为\(INF\)，费用为\(0\)。
对于每一组志愿者\((s_i, t_i, c_i)\)，考虑连边\((s_i, t_i + 1, INF, c_i)\)，这样意味着整个工作流中可以从额外管道中获取流量，将最大流调整到\(INF\)。
所以求得的最小费用肯定是在最大流量\(INF\)的前提下求得的，即为答案。