「BZOJ5415」「NOI2018」归程
题目链接题解首先我们尝试把不能被车经过的边删掉，得到了一张新图。这个新图上每一个连通块的答案都相同。 所以 Dijkstra 是首先要跑的。然后我们发现如果可以离线的话我们可以把边和询问放在一起排序，用普通的并查集维护一下每个连通块到 $1$ 节点的最短距离就可以了。 但是这题目要求强制在线怎么办？我们可以使用可持久化并查集来维护这个东西。 可持久化并查集用可持久化线段树来实现，非常简单。代...
题目链接题解首先我们尝试把不能被车经过的边删掉，得到了一张新图。这个新图上每一个连通块的答案都相同。 所以 Dijkstra 是首先要跑的。然后我们发现如果可以离线的话我们可以把边和询问放在一起排序，用普通的并查集维护一下每个连通块到 $1$ 节点的最短距离就可以了。 但是这题目要求强制在线怎么办？我们可以使用可持久化并查集来维护这个东西。 可持久化并查集用可持久化线段树来实现，非常简单。代...
如何维护区间我们都知道平衡树是一种很神奇的东西，可以用于维护动态的序列总信息，但是如果想维护其中的某一个区间的信息，我们该怎么做好呢？我们考虑换一种维护方式：平衡树的结构不是按照节点的值的大小来进行建树，而是以这个节点在序列中的位置为关键字来维护。也就是说对于平衡树中任意一个节点 $x$ ，左子树中的元素永远在它前面，右子树的元素永远在它后面。显然一个区间可以对应一个子树，所以我们要使用能提...
题目链接题目大意是对于每种物品被划分到不同的组里会产生不同的贡献，求一种最大的划分（这里的划分是连续一段划分到一起），并且要动态维护这个东西。我们首先考虑静态如何做这个东西，显然我们可以设出一个极为暴力的状态：$f(l,r,i,j)$ 表示燃料 $[l,r]$ 使用区间 $[i,j]$ 内的工作状态能得到的最大价值，直接 $O(4^3)$ 枚举中间点暴力转移一下就可以了。但是我们还要支持插入...
K-D Tree，全名k-dimensional Tree，是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。K-D Tree是二进制空间分割树的特殊的情况，以下是一棵二维空间上的 k-d tree：建树K-D Tree 的建树过程类似于平衡树：对于已知点集，求出其在某一维度上排序后的中间点，作为这个空间的分割点，然后把空间一分为二，再对每个部分...
众所周知 LCT 可以用来维护动态树的点权信息，但是总有一些题目让你维护动态树上的子树信息或者是链信息，就在这里拿一道经典的题目讲一讲。<h2>「UOJ207」共价大爷游长沙</h2>题目链接题目要求维护动态树和一个路径集合，询问某一条边是否被路径集合中所有的路径经过。首先我们考虑一下树是静态的怎么做：显然我们可以yy出一个随机化算法，我们可以对于每一条路径 $(u,...