莫队算法的优化

莫队算法的优化

我在之前的博客中已经介绍了莫队算法
之前所用的quescomp函数是这样的:

然而,当l指针从一个块移到下一个块时,r指针会从左到右再往左,这样就感觉不怎么好,所以可以把quescomp改成下面这样:

这样左端点编号为奇数的块右端点按从小到大排序,偶数的块从大到小,这样脑补一下,右端点总的移动距离会少一些,所以可以优化一些常数。

莫队算法的优化
Tagged on:     

4 thoughts on “莫队算法的优化

发表评论

电子邮件地址不会被公开。 必填项已用*标注