Skip to content

2D Mo's Algorithm

Two-dimensional Mo's algorithm, as the name suggests, means each state can be expanded in four directions.

In two-dimensional Mo's algorithm, each pointer movement involves operating on a row or a column of numbers. The specific implementation is similar to the ordinary one-dimensional Mo's algorithm and will not be repeated here. This section focuses on selecting the block size.

Block Size Selection

Let the number of queries be \(q\), the coordinates of the top-left corner of the current matrix be \((x_1,\ y_1)\), the coordinates of the bottom-right corner be \((x_2,\ y_2)\), and the block size be \(B\).

Then, pointer \(x_1\) moves \(\Theta(q\cdot B)\) times, while pointer \(y_2\) moves \(\Theta(n^4\cdot B^{-3})\) times.

Thus, we only need to set \(q\cdot B=n^4\cdot B^{-3}\), i.e., \(B=n\cdot q^{-\frac 14}\).

Note that the computed \(B\) may be \(0\), so special handling is required.

Finally, the time complexity of the computation part is \(\Theta(n^2\cdot q^{\frac 34})\), and adding the sorting process for queries, the total time complexity is \(\Theta(n^2\cdot q^{\frac 34}+q\log q)\).

Example 1

BZOJ 2639 Rectangle Calculation

Input an \(n\times m\) matrix, where each element of the matrix is an integer. There are \(q\) queries, each asking for the weight of a submatrix. The weight of the matrix is defined as follows: for an integer \(x\), if it appears \(p\) times in the matrix, it contributes \(p^2\) to the weight of the matrix.

Data range: \(1\leq n,\ m\leq 200\), \(0\leq q\leq 10^5\), \(|\) matrix element value \(| \leq 2\times 10^9\).

Solution Idea

First, discretize the values. During the two-dimensional Mo's algorithm, use an array to record the current occurrence count of each number.

Example Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

int n, m, q, a[201][201];
long long ans[100001];
int disc[250001], cntdisc;  // For discretization

int blocklen, counts[40001];
long long now;

struct Question {
  int x1, y1, x2, y2, qid;

  bool operator<(Question tmp) const {
    if (x1 / blocklen != tmp.x1 / blocklen) return x1 < tmp.x1;
    if (y1 / blocklen != tmp.y1 / blocklen) return y1 < tmp.y1;
    if (x2 / blocklen != tmp.x2 / blocklen) return x2 < tmp.x2;
    return y2 < tmp.y2;
  }
} Q[100001];

int Qcnt;

void mo_algo_row(int id, int val, int Y1, int Y2) {
  for (int i = Y1; i <= Y2; i++)
    now -= (long long)counts[a[id][i]] * counts[a[id][i]],
        counts[a[id][i]] += val,
        now += (long long)counts[a[id][i]] * counts[a[id][i]];
}

void mo_algo_column(int id, int val, int X1, int X2) {
  for (int i = X1; i <= X2; i++)
    now -= (long long)counts[a[i][id]] * counts[a[i][id]],
        counts[a[i][id]] += val,
        now += (long long)counts[a[i][id]] * counts[a[i][id]];
}

void mo_algo() {
  blocklen = pow(n * m, 0.5) / pow(q, 0.25);
  if (blocklen < 1) blocklen = 1;
  sort(Q + 1, Q + 1 + Qcnt);

  int X1 = 1, Y1 = 1, X2 = 0, Y2 = 0;
  for (int i = 1; i <= Qcnt; i++) {
    while (X1 > Q[i].x1) mo_algo_row(--X1, 1, Y1, Y2);
    while (X2 < Q[i].x2) mo_algo_row(++X2, 1, Y1, Y2);
    while (Y1 > Q[i].y1) mo_algo_column(--Y1, 1, X1, X2);
    while (Y2 < Q[i].y2) mo_algo_column(++Y2, 1, X1, X2);
    while (X1 < Q[i].x1) mo_algo_row(X1++, -1, Y1, Y2);
    while (X2 > Q[i].x2) mo_algo_row(X2--, -1, Y1, Y2);
    while (Y1 < Q[i].y1) mo_algo_column(Y1++, -1, X1, X2);
    while (Y2 > Q[i].y2) mo_algo_column(Y2--, -1, X1, X2);
    ans[Q[i].qid] = now;
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) cin >> a[i][j], disc[++cntdisc] = a[i][j];
  sort(disc + 1, disc + 1 + cntdisc);
  cntdisc = unique(disc + 1, disc + cntdisc + 1) - disc - 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      a[i][j] = lower_bound(disc + 1, disc + 1 + cntdisc, a[i][j]) - disc;
  cin >> q;
  for (int i = 1; i <= q; i++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    if (x1 > x2) swap(x1, x2);
    if (y1 > y2) swap(y1, y2);
    Q[++Qcnt] = {x1, y1, x2, y2, i};
  }

  mo_algo();
  for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
  return 0;
}

Example 2

Luogu P1527 [National Training Team] Matrix Multiplication

Given an \(n\times n\) matrix and \(q\) queries, each query asks for the \(k\)-th smallest number in a submatrix.

Data range: \(1\leq n\leq 500\), \(1\leq q\leq 6\times 10^4\), \(0\leq a_{i,j}\leq 10^9\).

First, similar to the previous problem, the entire matrix needs to be discretized. However, note that in addition to partitioning the values, the value range of the numbers also needs to be partitioned to compute the answer.

Here, odd-even ordering optimization is also required. For details, refer to Optimizations for Ordinary Mo's Algorithm.

For this problem, the time limit is not very lenient, so pay attention to code constant optimization. The computed block size is generally small; when \(n\) and \(q\) are at their maximum values, the block size is approximately \(11\). It can be set as a constant to save code execution time.

Example Code 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int n, q, a[501][501], ans[60001];
int disc[250001], cntdisc;  // For discretization
int nn;

int blockId[501], blocklen;               // Block decomposition
int rangeblockId[250001], rangeblocklen;  // Value range block decomposition
int counts[250001], countsum[501];        // Frequency of each value and block sum

struct Position {
  int x, y;
};

vector<Position> pos[250001];

struct Question {
  int x1, y1, x2, y2, k, qid;

  bool operator<(Question tmp) const {
    if (blockId[x1] != blockId[tmp.x1]) return blockId[x1] < blockId[tmp.x1];
    if (blockId[y1] != blockId[tmp.y1])
      return blockId[x1] & 1 ? y1 < tmp.y1 : y1 > tmp.y1;
    if (blockId[y2] != blockId[tmp.y2])
      return blockId[y1] & 1 ? y2 < tmp.y2 : y2 > tmp.y2;
    else
      return blockId[y2] & 1 ? x2 < tmp.x2 : x2 > tmp.x2;
  }
} Q[60001];

int Qcnt;

void mo_algo() {
  blocklen = 11;
  for (int i = 1; i <= n; ++i) blockId[i] = (i - 1) / blocklen + 1;
  rangeblocklen = n + 1;
  for (int i = 1; i <= nn; ++i) rangeblockId[i] = (i - 1) / rangeblocklen + 1;
  counts[a[1][1]] = countsum[rangeblockId[a[1][1]]] = 1;
  sort(Q + 1, Q + 1 + Qcnt);

  int L = 1, R = 1, D = 1, U = 1;
  for (int i = 1; i <= q; ++i) {
    while (R < Q[i].y2) {
      ++R;
      for (int i = U; i <= D; ++i)
        ++counts[a[i][R]], ++countsum[rangeblockId[a[i][R]]];
    }
    while (L > Q[i].y1) {
      --L;
      for (int i = U; i <= D; ++i)
        ++counts[a[i][L]], ++countsum[rangeblockId[a[i][L]]];
    }
    while (D < Q[i].x2) {
      ++D;
      for (int i = L; i <= R; ++i)
        ++counts[a[D][i]], ++countsum[rangeblockId[a[D][i]]];
    }
    while (U > Q[i].x1) {
      --U;
      for (int i = L; i <= R; ++i)
        ++counts[a[U][i]], ++countsum[rangeblockId[a[U][i]]];
    }
    while (R > Q[i].y2) {
      for (int i = U; i <= D; ++i)
        --counts[a[i][R]], --countsum[rangeblockId[a[i][R]]];
      --R;
    }
    while (L < Q[i].y1) {
      for (int i = U; i <= D; ++i)
        --counts[a[i][L]], --countsum[rangeblockId[a[i][L]]];
      ++L;
    }
    while (D > Q[i].x2) {
      for (int i = L; i <= R; ++i)
        --counts[a[D][i]], --countsum[rangeblockId[a[D][i]]];
      --D;
    }
    while (U < Q[i].x1) {
      for (int i = L; i <= R; ++i)
        --counts[a[U][i]], --countsum[rangeblockId[a[U][i]]];
      ++U;
    }
    int res = 1, cnt = 0;
    while (cnt + countsum[res] < Q[i].k && res <= rangeblockId[nn])
      cnt += countsum[res], ++res;
    res = (res - 1) * rangeblocklen + 1;
    while (cnt + counts[res] < Q[i].k && res <= nn) cnt += counts[res], ++res;
    ans[Q[i].qid] = disc[res];
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> q;
  nn = n * n;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      int x;
      cin >> x;
      a[i][j] = disc[++cntdisc] = x;
    }
  sort(disc + 1, disc + 1 + cntdisc);
  cntdisc = unique(disc + 1, disc + cntdisc + 1) - disc - 1;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      a[i][j] = lower_bound(disc + 1, disc + 1 + cntdisc, a[i][j]) - disc;
  for (int i = 1; i <= q; ++i) {
    int x1, y1, x2, y2, k;
    cin >> x1 >> y1 >> x2 >> y2 >> k;
    Q[++Qcnt] = {x1, y1, x2, y2, k, i};
  }

  mo_algo();
  for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用