Sqrt Decomposition : MO's Algorithm
The idea of MO’s algorithm is to pre-process all queries so that result of one query can be used in next query. O(m log m) preprocessing O(n √n) + O(m √n) = O((m + n) √n) processing all queries n - array size qlr - queries [L, R] addL - add current L addR - add current R removeL - remove current L removeR - remove current R runQ - run current query
|
// -----------------------------------------------------------------------------
// MO's Algorithm C#
// -----------------------------------------------------------------------------
class MOs
{
int N;
int[][] QLR;
Action<int> AddL, RemoveL, AddR, RemoveR, RunQ;
public MOs(int n, int[][] qlr, Action<int> addL,
Action<int> removeL,
Action<int> addR,
Action<int> removeR,
Action<int> runQ)
{
N = n;
QLR = qlr;
AddL = addL;
AddR = addR;
RemoveL = removeL;
RemoveR = removeR;
RunQ = runQ;
}
public void Run()
{
int blockSize = (int)Math.Sqrt(N);
int[] xQ = new int[QLR.Length];
for (int i = 0; i < xQ.Length; i++) xQ[i] = i;
Array.Sort(xQ, (p1, p2) => {
int cmp =
(QLR[p1][0] / blockSize).CompareTo(QLR[p2][0] / blockSize);
if (cmp == 0) cmp = QLR[p1][1].CompareTo(QLR[p2][1]);
return cmp;
});
int L = 0;
int R = 0;
for (int i = 0; i < xQ.Length; i++) {
while (L < QLR[xQ[i]][0]) { RemoveL(L); L++; }
while (L > QLR[xQ[i]][0]) { AddL(L); L--; }
while (R < QLR[xQ[i]][1]) { AddR(R); R++; }
while (R > QLR[xQ[i]][1]) { RemoveR(R); R--; }
RunQ(xQ[i]);
}
}
}
// -----------------------------------------------------------------------------