AIOJ

Two-dimensional Mo's algorithm, as the name suggests, allows each state to be extended in four directions.

In two-dimensional Mo's algorithm, moving a pointer operates on the values in one row or one column. The concrete implementation is similar to ordinary one-dimensional Mo's algorithm and will not be repeated here. The focus here is the choice of block length.

Block Length Selection

Let the number of queries be $q$ , let the coordinates of the upper-left corner of the current matrix be $(x_1,\ y_1)$ , let the coordinates of the lower-right corner be $(x_2,\ y_2)$ , and let the block length be $B$ .

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

Therefore, it suffices to set $q\cdot B=n^4\cdot B^{-3}$ , which gives $B=n\cdot q^{-\frac 14}$ .

Note that this calculation of $B$ may produce $0$ ; handle this as a special case.

Thus, the time complexity of the computation is $\Theta(n^2\cdot q^{\frac 34})$ . Including the query-sorting process, the total time complexity is $\Theta(n^2\cdot q^{\frac 34}+q\log q)$ .

Example 1

BZOJ 2639 Rectangle Calculation

Given an $n\times m$ matrix whose elements are all integers, there are $q$ queries, each asking for the weight of a submatrix. The weight of a matrix is defined as follows: if an integer $x$ occurs $p$ times in the matrix, it contributes $p^2$ to the weight of that matrix.

Data constraints: $1\leq n,\ m\leq 200$ , $0\leq q\leq 10^5$ , $|$ absolute value of a matrix element $| \leq 2\times 10^9$ .

Solution

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

Example code

#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, answer $q$ queries. Each query asks for the $k$ -th smallest number in a submatrix.

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

As in the previous problem, first discretize the entire matrix. Note, however, that this problem requires not only blocking the values but also blocking the value range in order to find the answer.

This problem also uses odd-even sorting for optimization; see ordinary Mo's algorithm for details.

For this problem, the time limit is not especially strict, so pay attention to constant factors in the code. The calculated block length is generally rather small: when both $n,\ q$ take their maximum values, it is about $11$ . It can be set directly as a constant to reduce code overhead.