传送门 $\text{Solution}$我们先考虑最朴素的 DP，令 $f_i$ 表示上一个仓库建设在第 $i$ 个点的最小花费。 我们有 \begin{aligned} f_i &= \min_{0\leq j时间复杂度为 $O(n^3)$ 严重超时，考虑用前缀和进行第一步优化： \begi ...

树状数组（Binary Indexed Tree），又名二叉索引树，Fenwick树，其处理的问题模型一般可以转化为如下形式：定义一个数组 $a[1 .. n ]$，并维护一下两个操作： 修改，给 $a[i]$ 加上某个增量 $delta$。 查询，询问某个前缀 $a[1.. index]$ 的和 ...

传送门 由于这道题是权限题，所以题面我也放在这里了（我不是权限狗）。 $\text{Description}$【题目背景】 　　小Q最近喜欢上了一款游戏，名为《舰队connection》，在游戏中，小Q指挥强大的舰队南征北战，从而成为了一名dalao。在游戏中，不仅船只能力很重要，搭配合适的装备更是 ...

可持久化数组是由可持久化线段树或可持久化平衡树实现的。这里先给出可持久化线段树的实现方法。 为了方便起见，处理的数组长度为5， 起始的数组元素为1~5，修改是将第一个位置的数组元素改为2。建树规则很简单，只要在叶子节点上写上该点的值就可以了。 先根据原数组建一棵线段树 第一次修改之后的线段树我们发现 ...

由于线段树在OI中的运用十分灵活，没有固定性的模板，这里就给出能够完成以下操作的线段树：1.给一段区间加上一个值2.询问一个区间内数值的总和$lazy-tag$是个好东西，要养成写$lazy-tag$的好习惯。 先码上一个链表版本的线段树：链表线段树很简单（不是假的），像我这样的蒟蒻就是因为静态数组 ...

传送门 $\text{Solution}$题目是可持久化并查集加强版，其实并没有加强，只是原题可以用离线算法水过，而这道题才是用来练可持久化并查集的板子题。首先对于学习可持久化并查集有一个先决条件，就是学会用可持久化线段树实现可持久化数组，如果不会的可以戳这。接下来我们就来讲讲怎么用可持久化数组实现 ...

传送门 $\text{Solution}$题目意思很简单，就是你有三种操作：1 u v w 从u向v连一条权值为w的有向边2 u L R w 从u向L至R的所有结点连一条权值为w的有向边3 u L R w 从L至R的所有结点向u连一条权值为w的有向边首先看到题目，马上就明白不是暴力能够解决的事情（毕 ...

矩阵的运算法则$ \huge + $ 加法，两个行数和列数分别相同的矩阵可以进行加法运算，Ans矩阵每个位置上的数为两个矩阵相应位置上的数的和$ \huge - $ 减法，与加法类似两个行数和列数分别相同的矩阵可以进行减法运算，Ans矩阵每个位置上的数为两个矩阵相应位置上的数的差$ \huge $ ...

$\text{Description}$有n个数列，每个数列长度可能不一样，同时有一个c，你有一种操作，让这n个数列中所有小于c的数都加1，所有等于c的数变成0.问你最少可以操作几次可以让这n个数列满足字典序. $\text{Solution}$我们可以发现，对于任意两个相邻的数列，操作数k有一个符 ...

浅析 LCA定义LCA（Least Common Ancestors），即最近公共祖先，指对于有根树 $T$ 的两个结点 $u$ 、$v$ ，最近公共祖先 $LCA(T, u, v)$ 表示一个结点 $x$, 满足 $x$ 是 $u$、$v$ 的祖先且 $x$ 的深度尽可能大。 下面给出一个自己画 ...