Java教程

莫队算法浅析

本文主要是介绍莫队算法浅析，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

莫队：著名 \(O(n\sqrt{n})\) 离线算法，思想基于分块。

做法

令 \(t = \sqrt{n}\) ，将区间左端点分成 \(t\) 块，按块从小到大排序，再将块内按从小到大排序。即：

bool compare(node s1 , node s2){
	if(s1.x / t < s2.x / t) return true;
	if(s1.x / t > s2.x / t) return false;
	return s1.y < s2.y;
}

之后双指针维护序列即可。

这篇关于莫队算法浅析的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航