Menci

「BZOJ 3809」Gty 的二逼妹子序列 - 莫队 + 分块

给一个序列，每次求 $[l, r]$ 之间权值在 $[a, b]$ 之间的不同的数的数量。

「JSOI2012」玄武密码 - SAM

给一个字符串 $S$，给一些字符串 $s_i$，求每个 $s_i$ 的最长的在 $S$ 中出现过的前缀的长度。

「BZOJ 3569」DZY Loves Chinese II - 随机化 + 线性基

给一个无向连通图，每次指定其中的 $k$ 条边，求如果将这些边删除，剩余的图是否仍然连通。

「BZOJ 1677」求和 - DP

给出一个 $N$，使用一些 $2$ 的若干次幂的数相加来求之。问有多少种方法。

「JSOI2010」部落划分 - Kruskal

在二维平面上给若干个点，将这些点划分为若干个区域，定义两个区域的距离为这两个区域之间最近点对的距离。求将这些点划分为 $k$ 个区域，使得最近的两个区域的距离最大值。

「BZOJ 3744」Gty 的妹子序列 - 分块 + 树状数组

给一个序列，每次询问 $[l, r]$ 的逆序对数，强制在线。

「SCOI2016」背单词 - Trie + 贪心

总共有 $n$ 个单词，对于一个序号为 $x$ 的单词（序号 $1 \ldots x - 1$ 都已经被填入）：

1. 如果存在一个单词是它的后缀，并且当前没有被填入表内，代价为 $n \times n$ 颗泡椒才能学会；
2. 当它的所有后缀都被填入表内的情况下，如果在 $1 \ldots x - 1$ 的位置上的单词都不是它的后缀，那么代价为 $x$；
3. 当它的所有后缀都被填入表内的情况下，如果 $1 \ldots x - 1$ 的位置上存在是它后缀的单词，所有是它后缀的单词中，序号最大为 $y$，那么代价为 $x - y$。

后缀自动机学习笔记

后缀自动机是一种有限状态自动机，它可以（且仅可以）接受一个字符串的所有后缀。

「SDOI2014」LIS - 最小割 + 网络流退流

给定序列 $A$，序列中的每一项 $A_i$ 有删除代价 $B_i$ 和附加属性 $C_i$。请删除若干项，使得 $A$ 的最长上升子序列长度减少至少 $1$，且付出的代价之和最小，并输出方案。

如果有多种方案，请输出将删去项的附加属性排序 $C_i$ 之后，字典序最小的一种。

「BZOJ 4499」线性函数 - 线段树

小 C 最近在学习线性函数，线性函数可以表示为 $f(x) = kx + b$。现在小 C 面前有 $n$ 个线性函数 $f_i(x) = k_ix+b_i$，他对这 $n$ 个线性函数执行 $m$ 次操作，每次可以：

1. M i K B 代表把第 $i$ 个线性函数改为 $f_i(x) = kx + b$；
2. Q l r x 返回 。