kal0rona on 有意思。之前做过一题是用矩阵树+高斯消元插值求本题的一维情况，本打算用继续这么做，后面发现 Lagrange 插值能做到 \(\Theta(n^5)\)，就学了一点新的东西。
首先，要认识到本题矩阵树出来之后可以得到一个二元多项式：
\[ \sum_{i = 0}^{n – 1} \sum_{j = 0}^{n – 1} a_{i, j} x^i y^j \]
Read More kal0rona on kal0rona on 如果你手上有一堆散点，然后你可以用这个公式拟合出一个函数：
\[ f(x) = \sum_{i = 1}^n y_i \prod_{j \neq i}^n \frac{x – x_j}{x_i – x_j} \]
Read More kal0rona on kal0rona on 斜率优化其实不是很难，可以理解为在平面上的一些点作为决策点，而你现在有一条斜率为 \(k\) 的直线，你需要使其经过一个合适的点，使得这条线的截距最大/最小化。这个显然可以使这些点组成一个上/下凸包、然后二分找到斜率相近的那条线段进行转移。
Read More kal0rona on 先差分，然后再来做这个不相交子串匹配的问题。
我们可以考虑用线段树来维护 endpos 集合，然后用启发式合并的方式来计算一个后缀点与当前点集之间产生的贡献。有两种情况：