Here’s something encrypted, password is required to continue reading.
-
线性基
Here’s something encrypted, password is required to continue reading.
-
最小割树
最小割树Intro图上本质不同的最小割只有 种，用树边来表达 有时候需要多次询问两点之间的最小割，可以用最小割树解决 暴力算法是 ，最小割树是 的 算法流程 随便选择当前原图连通块的点跑最小割，在两点的树图连边，边权为最小割 将 分开，分别继续递归处理 当点集大小为 时停止处理 注：每次求最小割之前需要恢复原图 原图两点之间的最小割=树图两点之间简单路径的最小边权 模板题 这个题数... -
省选模拟赛补题
Here’s something encrypted, password is required to continue reading.
-
网络流复建
Here’s something encrypted, password is required to continue reading.
-
虚树
虚树Intro【洛谷日报#185】浅谈虚树 - SSerxhs 的博客 - 洛谷博客 (luogu.com.cn) 对于一棵树，如果我们只询问其中一些点，且 可以接受，我们就考虑每次建出虚树 一颗虚树包含所有询问节点+所有询问节点的 ，总节点数 ，最劣情况就是都是虚树叶子 称所有询问节点为关键点 构建方法可以看上面那篇博客，大致就是先按 排序，然后每次增量构造 12345678910... -
长链剖分
长链剖分Intro和重链剖分差不多 定义 长儿子为从该节点开始有最长向下路径的节点 从这个结点到长儿子的边为重边，若干条首尾衔接的重边构成长链 链顶为一条链顶为这条链深度最小的节点 链底为一条链顶为这条链深度最小的节点 一个节点到根节点的至多经过 条链 Problem求 级祖先P5903 【模板】树上 K 级祖先 任意一个点的 级祖先所在链的链长一定 首先预处理出每个节点在哪条链上，... -
DFA 全家桶
Here’s something encrypted, password is required to continue reading.
-
串串进阶
Hash对一种图形进行 就是要体现这个图的结构，主要表现在 “相邻” 结构，从而隐式的表达图结构 树 Hash对于一棵树，就是通过子树表达相邻 对于有根树，可以直接从根开始，无根树可以从重心开始，如果有两个，就都存下来比较 函数： 1234567891011121314151617181920212223242526272829303132333435363738394041424344... -
P7811 [JRKSJ R2] 你的名字。
看到取模直接根号分治 设阈值为 ：离线后枚举每个 ，区间最小值随便做， 笔者直接大力分块 ：我们可以发现问题等价于求 只有 个，总询问个数 ，需要 查询最小值 我们考虑离线来降低查询复杂度，首先针对值域上的问题可以扫描线消一维，这个时候修改次数只有 ，可以从修改入手 我们把询问挂在值域上，然后从大到小扫，我们需要 区间最小值，这只有 RMQ 可以做到，但是我们知道 RMQ 不...