前置 二叉搜索树 BST BST 有以下两个性质： 二叉树 节点的权值始终为 left<root<right。 堆 Heap 所有父亲的值都不大于两个儿子的值的完全二叉树，叫做堆。 即 root \leq left 且 root \leq right。 树堆 Treap Treap 的节点维护两个信
1. 介绍与引入 没有前言，懒得写了。 根号分治，本质是平衡规划思想（大纲 9 级），在预处理和询问复杂度中寻找平衡，我们通常用根号作为问题规模的分界线。我们确定一个界限 B，小于 B 的暴力预处理，大于的回答一次时间只需要 \dfrac{n}{B}\le \sqrt{n} ，那么整个题目就可以做到
本来感觉挺神秘的一个东西， 学完了似乎没有多难， 放几个板子随便写写吧（今天数学不想做题） 从最最最最人尽皆知的区间第 k 大问题开始吧 引入 如果我想问你一个序列中的区间的第 k 大，你会如何？ 显然我们直接二分就行（主席树学傻的滚） 时间复杂度为 O(nlogn) 感觉挺不错的呢 但是如果我们有
发布于 2025-07-15
0.前言 省流：\text{Rk } 1 \to \text{Rk 3},305 \to 255。 T1 虎爷ywk 判断是否存在正整数 n，使得 k|n^2，但 k 不能整除 n，若存在输出最小的 n，否则输出 -1。 1\le k \le 10^{12}
才发现自己之前看的 2-SAT 模板题题解赤到石了，到最后不过是背过了板子题的代码罢了。 做了一些题之后渐渐懂了一些，有了一些自己的见解。 它能解决一类问题类似一个序列，每个位置只有两个取值，然后取值间有一些限制，求解其是否有解以及求一个可行解。 考虑每个位置拆分为两个点，分别为 i 和 \neg
发布于 2025-07-05
可能更好的阅读体验 0. 前言 后缀数组是信息学竞赛中解决字符串匹配的一大利器，其思想和实现非常简单。虽然倍增加排序的思想很简单，但是它的拓展 ht 数组功能及其强大并且适用性广，在 OI 范围内广泛应用。 以下应用魏老师的一句话： 几乎所有字符串算法都存在一个共性：基于所求信息的特殊性质与已经求出
.png)
