Skip to content

Mo's Algorithm Secondary Offline

Overview

Sometimes we encounter problems that seem suitable for Mo's algorithm, but their single transition is not \(O(1)\). In such cases, directly applying Mo's algorithm, even with adjusted block sizes, will lead to incorrect complexity.

If the contribution of each transition to the answer can be differenced, we can break down these transitions, process them offline, and handle them in batches using other algorithms.

Let \(f(x, l, r)\) denote the contribution of \(x\) to \([l, r]\).

For example, when expanding the current interval \([l, r]\) to \([l, r + 1]\), we need \(f(a_{r + 1}, l, r)\). If it can be differenced, we can write it as \(f(a_{r + 1}, 1, r) - f(a_{r + 1}, 1, l - 1)\). The first term can be preprocessed for each \(r\), and the latter term can be stored offline at the corresponding \(l - 1\), then processed by scanning line from small to large. Other transition directions can be handled similarly.

This technique of further offloading transitions within the already offline Mo's algorithm is called Mo's Algorithm with Second Offline.

Let's understand it through concrete problems.

Example Problems

Luogu P5047 [Ynoi2019 Mock Contest] Yuno loves sqrt technology II

You are given a sequence \(a\) of length \(n\) and \(m\) queries. Each query asks for the number of inversions in an interval.

Constraints: \(1 \leq n,m \leq 10^5\), \(0 \leq a_i \leq 10^9\).

Direct Mo's algorithm requires at least \(O(\log n)\) per transition. Observation shows that each transition requires the information "the rank of a number within a certain interval", which can be differenced with respect to the interval. Thus, consider second offline.

Expanding \([l, r]\) to \([l, r + 1]\) requires the number of elements greater than \(a_{r + 1}\) in \([l, r]\). Let \(f(x, r)\) be the number of elements greater than \(a_x\) in \([1, r]\), and \(g(x, r)\) be the number of elements smaller than \(a_x\) in \([1, r]\). Then the change in answer can be written as \(f(r + 1, r) - f(r + 1, l - 1)\).

Similarly, shrinking \([l, r]\) to \([l, r - 1]\) gives \(-f(r, r - 1) + f(r, l - 1)\); expanding \([l, r]\) to \([l - 1, r]\) gives \(g(l - 1, r) - g(l - 1, l - 2)\); shrinking \([l, r]\) to \([l + 1, r]\) gives \(- g(l, r) + g(l, l - 1)\).

For terms like \(f(x, x - 1)\) and \(g(x, x - 1)\), we can preprocess them in \(O(n \log n)\) using a Fenwick tree. For the remaining \(f(x, p)\) and \(g(x, p)\) terms, we store \(x\) offline at \(l\) for batch processing.

A space optimization: For each query, the \(x\) values stored at \(p\) form a contiguous segment. Thus, we don't need to store every single move; only the adjusted segment is needed. This reduces space from total moves \(O(n\sqrt{m})\) to number of queries \(O(m)\).

Now we handle the second offline problem: adding numbers to a set and querying the rank of a number in the set. Mo's algorithm moves endpoints \(O(n\sqrt{m})\) times, but the array length is only \(O(n)\). Consider using a value domain block data structure with \(O(\sqrt{n})\) insertion and \(O(1)\) query to solve this.

Thus, we solve the problem in \(O(n \sqrt{m} + n \sqrt{n})\) time and \(O(n + m)\) space.

Finally, note that we compute the change in answer per step, not the answer itself. Prefix sums are needed to obtain the final answers.

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>

constexpr int MAX = 1e5 + 5;
constexpr int MAXX = 4e2 + 5;
constexpr int MX = 1e5;
typedef long long ll;

int n, m, sz, _sz;
int a[MAX], b[MAX], bl[MAX], st[MAXX], ed[MAXX], b1[MAXX], b2[MAX], p1[MAX],
    p2[MAX];
ll ans[MAX];

struct N {
  int l, r, id, x, y;
};

std::vector<N> v[MAX];

struct Q {
  int l, r, id;
  ll ans = 0;
} q[MAX];

bool cmp(Q a, Q b) {
  if (a.l / _sz != b.l / _sz) {
    return a.l < b.l;
  }
  return ((a.l / _sz) & 1) ? a.r < b.r : a.r > b.r;
}

void init() {
  sz = sqrt(MX);
  for (int i = 1; i <= sz; ++i) {
    st[i] = (MX / sz) * (i - 1) + 1;
    ed[i] = (MX / sz) * i;
  }
  ed[sz] = MX;
  for (int i = 1; i <= sz; ++i) {
    for (int j = st[i]; j <= ed[i]; ++j) {
      bl[j] = i;
    }
  }
}

void clear() {
  memset(b1, 0, sizeof(b1));
  memset(b2, 0, sizeof(b2));
}

void mdf(int x) {
  for (int i = bl[x]; i <= sz; ++i) {
    ++b1[i];
  }
  for (int i = x; i <= ed[bl[x]]; ++i) {
    ++b2[i];
  }
}

int qry(int x) {
  if (!x) {
    return 0;
  }
  return b1[bl[x] - 1] + b2[x];
}

int main() {
  scanf("%d%d", &n, &m);
  init();
  _sz = sqrt(m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  std::sort(b + 1, b + n + 1);
  int len = std::unique(b + 1, b + n + 1) - b - 1;
  for (int i = 1; i <= n; ++i) {
    a[i] = std::lower_bound(b + 1, b + len + 1, a[i]) - b;
  }
  for (int i = 1; i <= n; ++i) {
    p1[i] = qry(a[i] - 1);
    p2[i] = qry(n) - qry(a[i]);
    mdf(a[i]);
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &q[i].l, &q[i].r);
    q[i].id = i;
  }
  std::sort(q + 1, q + m + 1, cmp);
  clear();
  for (int i = 1, L = 1, R = 0; i <= m; ++i) {
    int l = q[i].l, r = q[i].r;
    if (L > l) {
      v[R].push_back({l, L - 1, i, 1, 0});
    }
    while (L > l) {
      --L;
      q[i].ans -= p1[L];
    }
    if (R < r) {
      v[L - 1].push_back({R + 1, r, i, -1, 1});
    }
    while (R < r) {
      ++R;
      q[i].ans += p2[R];
    }
    if (L < l) {
      v[R].push_back({L, l - 1, i, -1, 0});
    }
    while (L < l) {
      q[i].ans += p1[L];
      ++L;
    }
    if (R > r) {
      v[L - 1].push_back({r + 1, R, i, 1, 1});
    }
    while (R > r) {
      q[i].ans -= p2[R];
      --R;
    }
  }
  for (int i = 1; i <= n; ++i) {
    mdf(a[i]);
    for (N j : v[i]) {
      for (int k = j.l; k <= j.r; ++k) {
        if (j.y == 0) {
          q[j.id].ans += j.x * qry(a[k] - 1);
        } else {
          q[j.id].ans += j.x * (i - qry(a[k]));
        }
      }
    }
  }
  for (int i = 2; i <= m; ++i) {
    q[i].ans += q[i - 1].ans;
  }
  for (int i = 1; i <= m; ++i) {
    ans[q[i].id] = q[i].ans;
  }
  for (int i = 1; i <= m; ++i) {
    printf("%lld\n", ans[i]);
  }
}
Luogu P5501 [LnOI2019] Come and welcome, go and no farewell

Multiple queries: For interval \([l, r]\), compute the sum of "Abbi values" of all numbers.

The Abbi value of \(a_i\) is defined as: if \(a_i\) is the \(k\)-th smallest in query interval \([l,r]\), then its Abbi value equals \(k \cdot a_i\).

Let \(f(x,r)\) be the sum of numbers greater than \(a_x\) in \([1,r]\), and \(g(x,r)\) be the count of numbers greater than \(a_x\) in \([1,r]\). When moving the right endpoint to the right, the contribution is \(f(r,r-1)-f(r,l-1) + a_r(r-l+ 1-(g(r,r-1)-g(r,l-1)))\). Other directions can be derived similarly.

The terms \(f(r, r - 1)\) and \(g(r, r - 1)\) can still be preprocessed. The rest are stored offline at the other endpoint for scanning line processing. It's clear that we still need to handle \(O(n)\) insertions and \(O(n\sqrt{m})\) rank queries, so again use value domain blocks.

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>

constexpr int MAX = 1e5 + 5;
constexpr int MAXX = 4e2 + 5;
constexpr int MX = 1e5;

typedef long long ll;

ll n, m, sz, _sz, sm;
ll st[MAXX], ed[MAXX], bl[MAX], a[MAX], ans[MAX], sm1[MAXX], sm3[MAXX],
    sm2[MAX], sm4[MAX], s[MAX], pre[MAX];

void init() {
  sz = sqrt(MX);
  for (int i = 1; i <= sz; ++i) {
    st[i] = (MX / sz) * (i - 1) + 1;
    ed[i] = (MX / sz) * i;
  }
  ed[sz] = MX;
  for (int i = 1; i <= sz; ++i) {
    for (int j = st[i]; j <= ed[i]; ++j) {
      bl[j] = i;
    }
  }
}

void mdf(ll x) {
  sm += x;
  for (int i = bl[x]; i <= sz; ++i) {
    ++sm1[i];
    sm3[i] += x;
  }
  for (int i = x; i <= ed[bl[x]]; ++i) {
    ++sm2[i];
    sm4[i] += x;
  }
}

ll qry(ll x) {
  if (!x) {
    return 0;
  }
  return sm1[bl[x] - 1] + sm2[x];
}

ll _qry(ll x) {
  if (!x) {
    return 0;
  }
  return sm3[bl[x] - 1] + sm4[x];
}

void clear() {
  sm = 0;
  memset(sm1, 0, sizeof(sm1));
  memset(sm2, 0, sizeof(sm2));
  memset(sm3, 0, sizeof(sm3));
  memset(sm4, 0, sizeof(sm4));
}

struct Q {
  ll l, r, id, ans;
} q[MAX];

struct N {
  ll l, r, id, x;
};

std::vector<N> v[MAX];

bool cmp(Q a, Q b) {
  if (a.l / _sz != b.l / _sz) {
    return a.l < b.l;
  } else {
    return ((a.l / _sz) & 1) ? a.r < b.r : a.r > b.r;
  }
}

int main() {
  scanf("%lld%lld", &n, &m);
  _sz = n / sqrt(m);
  init();
  for (int i = 1; i <= n; ++i) {
    scanf("%lld", &a[i]);
    s[i] = s[i - 1] + a[i];
  }
  for (int i = 1; i <= n; ++i) {
    pre[i] = qry(a[i] - 1) * a[i] + sm - _qry(a[i]);
    mdf(a[i]);
  }
  clear();
  for (int i = 1; i <= m; ++i) {
    scanf("%lld%lld", &q[i].l, &q[i].r);
    q[i].id = i;
  }
  std::sort(q + 1, q + m + 1, cmp);
  for (int i = 1, L = 1, R = 0; i <= m; ++i) {
    int l = q[i].l, r = q[i].r;
    if (L > l) {
      v[R].push_back({l, L - 1, i, 1});
    }
    while (L > l) {
      --L;
      q[i].ans -= pre[L];
    }
    if (R < r) {
      v[L - 1].push_back({R + 1, r, i, -1});
    }
    while (R < r) {
      ++R;
      q[i].ans += pre[R];
    }
    if (L < l) {
      v[R].push_back({L, l - 1, i, -1});
    }
    while (L < l) {
      q[i].ans += pre[L];
      ++L;
    }
    if (R > r) {
      v[L - 1].push_back({r + 1, R, i, 1});
    }
    while (R > r) {
      q[i].ans -= pre[R];
      --R;
    }
  }
  for (int i = 1; i <= n; ++i) {
    mdf(a[i]);
    for (N j : v[i]) {
      for (int k = j.l; k <= j.r; ++k) {
        q[j.id].ans += 1ll * j.x * (qry(a[k] - 1) * a[k] + sm - _qry(a[k]));
      }
    }
  }
  for (int i = 2; i <= m; ++i) {
    q[i].ans += q[i - 1].ans;
  }
  for (int i = 1; i <= m; ++i) {
    ans[q[i].id] = q[i].ans + s[q[i].r] - s[q[i].l - 1];
  }
  for (int i = 1; i <= m; ++i) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用