Charles Wu的博客

终于体会到了“看了题解都可能写不出来”的绝望了——CF925E May Holidays。

自以为已经对“分块”的思想有了一定掌握，到头来发现自己还只会最基本的、应用最广泛的值域分块。只是题见得不够多罢了。

考虑一种实际操作中不会使用的求区间第$k$大的算法。设块长为$S$，我们将序列分成$\mathrm{O}(\dfrac{n}{S})$块，每一块内直接对元素排序。对于一个询问$[l, r]$，我们二分答案。猜测答案为$d$，在中间的每一整块内二分出$\leq d$的元素数量，两侧暴力查找。这样的复杂度是$\mathrm{O}(\dfrac{len}{S} \log^2 n+S \log n)$的，其中$len$代表区间长。

这告诉我们，分块的目的不仅可以让较大的值域范围内的统计变得更高效，还可以使得元素（部分）有序，适用范围更加广泛。就连分块这种暴力数据结构使用时都需灵活变通，其他算法又何尝不是如此。

（更多…）

昨天考试完成T4时，明明想出了正解，但又以为二叉堆时间复杂度过高不敢实现……白白浪费了几十分钟时间。事后实现，发现完全没有技术上的问题。

具体来讲，通过同时保存指向每个元素在堆中当前位置的指针，可以$\mathrm{O}(\log n)$地修改和删除特定节点，以及常规的$\mathrm{O}(\log n)$的弹出栈顶、插入等操作，$\mathrm{O}(1)$地查询堆顶元素。

下面就以动态修改无向图中每个点的度并查询最小度的点为例实现一个这样的二叉堆。

（更多…）

基数排序是一种非比较的排序算法。它基于对每个子关键字在值域上的计数实现整体的排序。对于整数，可以在$\mathrm{O}(kn + \sum\limits_{i=1}^{k}w_i)$的线性时间内完成排序，其中$w_i$为每个关键字的值域大小。

以下代码将对int范围内的整数，以前$16$位和后$16$位为关键字进行排序。可以发现，在数据个数$n \leq 7\times 10^4$，其表现不如基于比较的快速排序算法。因此，在值域很大而数据较少时，应合理调整策略。

（更多…）

说来惭愧。从国庆到现在，至少有3个人试图把我讲懂期望，但我还是只明白最基本的定义，根本不会做题。

今天发现一篇入门级别的数学期望讲解，在此转载。