可持久化线段树(在中国国内信息学竞赛社区中又称总书记树、主席树或函数式线段树)是一种可持久化数据结构（Persistent data structure）.
2019-11-10
CSP-S 2019 冲刺训练计划
根据 luogu-problem-list 2.0 版本 制作
2019-10-26
CSP-S 2019 训练略记
CSP-S 2019 训练略记。OI Forever！
2019-10-26
肥城一中FOI 2019级宣传
OI是什么？信息学奥林匹克竞赛(OI,Olympiad in Informatics)。
与大家熟知的数学、物理、化学、生物竞赛合称为高中五大学科竞赛。
肥城一中FOI为学校官方组织，也是唯一的官方社团，又名信息学奥赛小组。
OI学什么？通
2019-09-20
【笔记】基于链式前向星的图论算法（三） 拓扑排序
有向无环图(DAG)可用来表示各种事物的顺序。比如以各项工作为顶点，用有向边来表示工作顺序。
如果对这种表示顺序关系的DAG进行拓扑排序， 我们便能得到一个恰当的工作顺序。
拓扑排序不是用于将n个数从小到大排序，而是对于一个DAG，对图上的
2019-09-13
【笔记】基于链式前向星的图论算法（二） 最短路
Part 1 单源最短路（SSSP）DijkstraDijkstra只能用于无负权边的图。
设图$G=(V,E)$所有顶点的集合为$V$，起点为$s$,最短路径树中包含的顶点集合为$S$。
在各计算步骤中，我们将选岀最短路径树的边和顶点并将
2019-09-13
【笔记】基于链式前向星的图论算法（一） 搜索
Part 0 缘起近日整理笔记时发现，初学时的图论算法都是基于邻接矩阵储存的，使用时非常不方便。所以就写了这篇博文，聊作图论学习的回顾。
Part 1 图的链式前向星表示链式前向星又称为邻接表的静态建表方式，其最开始确实是基于前向星，是以提
2019-09-08
【笔记】C++的常数优化技巧
Part 0 时间复杂度常数优化的意义在科学研究意义上，时间复杂度的常数优化并不是十分重要的。
但在信息学竞赛中，同样的复杂度为$O(n^2)$的程序，对于一组 $n=5000$ 的数据，有的可能常数为20，需要运行1000ms，有的可能常
2019-09-08
题解 T93279 【最长上升子树链】
传送门
30%的题解：
这棵树是一个链，所以直接做一遍LIS和LDS，经典DP算法，不多赘述。
60%的题解：
$N<=1000$,可以直接$n^2$地做满分题解所说的DP。
满分题解：
$F1[i]$表示以从以$i$为根节点的子
2019-08-22
题解 T93270 【轰炸城市】
传送门
30%的题解：
直接每次询问枚举所有点。
60%的题解：
坐标值很小，可以尝试用链表，可以做到$O(n)$的时间复杂度
100%的题解：
$map$套$multiset$
$X$坐标开个$mapx$，里面存的是每个$X$坐标的
2019-08-20
题解 T93222 【生成树】
传送门
30%的题解：
是一棵树，所以只要枚举根，然后计算代价即可
100%的题解：
$vals[S]$表示集合$S$的权值和
设计状态$F[S][h]$, 表示现在已经选择了的点的集合是$S$，$h$表示当前深度
枚举S的补集的子集
2019-08-20
题解 T93336 【最短路】
传送门
30%的做法
floyd预处理出每两点间的最短路,每次询问$O(1)$回答
复杂度$O(n^3+q)$
另外20%的做法
树的情况
对于$u,v$的最短路，求出他们的LCA为$k$，$ans=d[u]+d[v]-2*d[k
2019-08-20