动态树问题：维护一个森林，支持删除某条边，加入某条边并保证时刻是一个森林，我们需要维护森林的一些信息，一般的操作有询问两点连通性，询问两点路径的权值和，修改某点的权值。 基本介绍$LCT$是用来解决动态树问题的数据结构，各种操作的时间复

简单介绍伸展树（$splay$），也叫分裂数，是一种平衡二叉树，能在$O(log\ n)$的时间复杂度内完成插入，查找和删除操作，比较好写而且很实用，$LCT$也经常借助$splay$来实现，是一种在竞赛中比较常用的数据结构。本篇就来给大

可并堆，又叫左偏树，是一种支持合并的堆，以下内容基于小根堆（即根节点最小，大根堆类似），它支持以下功能： 求一个数所在堆的根节点（复杂度同并查集路径压缩） $O(1)$求最小值 $O(log\ n)$合并两个堆 $O(log\ n)$删除

先由一道例题引入：消耗战 对于这个问题的每个询问，我们直接树形$DP$就很容易解决了，然而，问题就在于如果我们每次$DP$都遍历整个树，那时间复杂度就爆炸了，但我们发现我们每次询问涉及到的点很少，这时就引入了我们的虚树，我们只需要把我们需要

首先，我们由一道题引入：小L打怪兽 很明显，对于这道题，$k=1$时我们要求的就是一个完全背包问题，但$1\le k\le100$，这时我们可以考虑多开一位状态，用$dp[i][j]$表示花费$i$体力情况下第$j$优解，我们知道在完全背包

先把遇到的问题放出来，然后再解决问题。 题目链接：Riddle 很明显，这是一道$2-SAT$问题，每条边至少有一个端点是关键点，若我们用$x$表示$x$是关键点，$x+n$表示$x$不是关键点，则对于一条边$x-y$，我们可以得到$x+n

后缀自动机，又称为SAM，是个有限状态自动机，我们可以把它看作一张有向拓扑图。由一个起点、若干终点组成。原串的所有子串和从SAM起点开始的所有路径一一对应，不重不漏。所有到达终点的路径就是原串的一个后缀。其中，每个点包含若干子串，每个子串

后缀数组常用的算法有两种，一种是倍增，一种是DC3，其中DC3是线性的，不过代码更恶心，常数也比较大，这里本人就先讲一下倍增的做法，虽然时间复杂度略差，不过还是很好用的。

本文章以线段树的拓展为主，不会讲解基础内容。另外本人目前比较忙，将在军训和第三学期后更新内容，现只列出大纲和例题。 线段树妙用HH的项链 喵星球上的点名 多tag后效性处理维护序列 线段树合并Dominant Indices 线段树分裂Ma

哈希是一种映射方法，我们用哈希把万物映射成一个整数值，字符串哈希就是把字符串映射为一个整数值，这样我们就能快速判断两个字符串是否相同。字母集$T$就是我们用到所有字母的集合，$|T|$就是其大小。$H$为哈希函数,$S$为字符串，$n$为

这篇文章我们不再讲解并查集的基础知识，主要讲解并查集的一些拓展用法，需要补一下基础知识的同学我推荐这一篇文章：并查集，另外这篇文章里讲到的按秩合并，也可以是把小的集合合并到大的集合上面，这样更容易代码实现，我们只需多维护一个集合的大小就可