莫队算法浅析(Analysis of Mo team algorithm)

莫队:著名 \(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;
}

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

————————

Mo Dui: the famous \ (O (n \ sqrt{n}) \) offline algorithm is based on blocking.

practice

Let \ (t = \ sqrt{n} \), divide the left end point of the interval into \ (t \) blocks, sort the blocks from small to large, and then sort the blocks from small to large. Namely:

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;
}

After that, the double pointer maintenance sequence can be used.