如何正确判断二分边界？ 常见问题 while内条件是\(\leq\)还是\(<\) left和right的修改时用不用加\(1\)减\(1\) 例题分析 例：给定一个正整数\(n(1\leqn\leq1,000)\)。 第二行输入\(n\)个整数\(num_i(0\leqnum_i\leq10,000)\)，保证严格单调递增，第三行输入一个整数\(k(0\leqk\leq10,000)\)。 若数列中有与\(k\)相等的数，输出其下标，否则输出No。 一般来说，我们将二分分为左闭右闭，左闭右开两种类型。 左闭右闭 首先我们根据上面容易出现的两个问题进行分析。 因为当出现leftri...

注：本文章假设读者已经学会基础的高斯消元法 引入 高斯约旦消元法是高斯消元法的一种，一般用于求解线性方程组。 对于一个线性方程组 \[\begin{cases}x+3y+4z=5\\x+4y+7z=3\\9x+3y+2z=2\end{cases}\] 我们可以将其写成一个增广矩阵的形式 \[\left[\begin{array}{ccc|c}1&3&4&5\\1&4&7&3\\9&3&2&2\\\end{array}\right]\] 我们知道，高斯消元是将增广矩阵等号左边部分化成一个阶梯化矩阵。这样可以轻...

引入 在一条链中，二叉查找树的时间复杂度就会退化成\(O(n)\)，这时我们就需要平衡树来解决这个问题。 \(Splay\)（伸展树）是平衡树的一种，它的每一步插入、查找和删除的平摊时间都是\(O(\logn)\)，出于对编程复杂度和算法性能的考虑，这是OI中常用的算法。 性质 \(Splay\)本质上还是对二叉查找树的优化。所以它也具备二叉查找树的性质，即左子树任意节点的值\(<\)根节点的值\(<\)右子树任意节点的值。 操作 数组含义 root tot fa[i] ch[i][0] ch[i][1] val[i] size[i] cnt[i] 根节点编号 节点数...

Tip：建议完成LuoguP3919后阅读。 目录 模板：静态区间\(k\)小值 模板：动态区间\(k\)小值 BZOJ3207：花神的嘲讽计划 疯狂的颜色序列 SPOJ10628：Countonatree LuoguP3302森林 模板题：静态区间\(k\)小值 思路引导 首先我们想一想，如何用线段树求数列\(k\)小值。 我们可以建一棵权值线段树，由于权值线段树的结点表示的是该结点指向的区间的数的数量，我们就可以直接使用一种类似二分的方法查询\(k\)小值。 假如你要查询第\(5\)小的数，如果你发现左儿子有\(4\)个数，那么就直接放弃左儿子去右儿子查找；反之，如果左儿子有\(7\)...