Standard Mo's Algorithm
Concept
The standard Mo's algorithm can solve certain interval problems that do not require online processing. It optimizes complexity by processing queries in an optimal order using brute force.
Consider block division. Divide the array into several blocks of length $ \sqrt{n} $. Sort the queries based on the block number of the left endpoint as the primary key and the right endpoint as the secondary key in ascending order. This approach results in an optimal time complexity of $ O(n\sqrt{n}) $.
Mo's algorithm generally requires efficient point movement, but there are two scenarios where optimization is possible:
- When one operation is simple, consider rollback Mo's algorithm.
- If the problem satisfies the subtractive property, consider Mo's algorithm with two passes.
Example
P3901 Find Different Numbers
This approach typically requires discretization and a bucket to be used.
Directly discuss the transfer of endpoints using the bucket.
Note that the initial values for $ l, r $ are set to $ 1, 0 $.
Modified Mo's Algorithm
Concept
Consider handling modifications offline.
Add a pointer $ k $ to the standard Mo's algorithm, representing the current interval after $ k $ modifications, with $ k $ initially set to $ 0 $.
When processing queries, move the modification pointer along with the interval pointer.
Optimization
It is difficult to optimize directly, so consider traditional techniques to adjust the block size.
Assume the block size is $ n^x $, where $ x $ satisfies $ 0 < x < 1 $, and the number of operations $ m $ is of the same order as $ n $.
Consider the worst-case time complexity when moving the $ l $ pointer:
-
When both $ l $ and $ r $ pointers move within a block:
The worst-case time complexity is $ O(n^x) $. With $ O(n) $ queries, the total time complexity is $ O(n^{x + 1}) $.
-
When the $ l $ pointer moves to subsequent blocks:
Each block movement has a time complexity of $ O(n^x) $. There are $ O(\frac{n}{n^x}) $ such blocks, resulting in a worst-case time complexity of $ O(n) $.
Thus, the worst-case time complexity for the $ l $ pointer is $ O(x + 1) $.
Next, consider the worst-case time complexity for moving the $ r $ pointer, which is added to the analysis of the $ l $ pointer without affecting the overall complexity:
-
When both $ l $ and $ r $ pointers move within a block:
Each pointer can move $ O(n^x) $ positions. With $ \frac{n}{n^x} $ blocks, the total time complexity is $ O(n^{2x} \times \frac{n}{n^x}) $, which simplifies to $ O(n^{2 - x}) $.
-
When the $ l $ pointer moves within a block and the $ r $ pointer moves to subsequent blocks:
Each block movement for the $ r $ pointer has a time complexity of $ O(n^x) $. In the worst case, $ \frac{n}{n^x} $ blocks need to be traversed.
Since the right endpoint is sorted in ascending order, each block may take $ O(n) $ time. The worst-case complexity approaches $ O(\frac{n}{n^x} \times n) $, which simplifies to $ O(n^{2 - x}) $.
-
When the $ l $ pointer moves to subsequent blocks:
The worst-case time complexity is $ O(n) $. Assuming each block contributes once, the total time complexity is $ O(n^{2 - x}) $.
Thus, the worst-case time complexity for the $ r $ pointer is also $ O(n^{2 - x}) $.
Finally, consider the worst-case time complexity for the $ k $ pointer:
-
When $ l $ and $ r $ pointers move within a block:
The $ k $ pointer increases according to the sorting rule, with a worst-case time complexity of $ O(n) $.
-
When the $ l $ pointer moves within a block:
The $ r $ pointer may move to subsequent blocks, with each movement having a worst-case time complexity of $ O(n) $.
Based on previous estimates, each movement of $ l $ and $ r $ pointers may take $ O(n^{2 - 2x}) $, and each movement of the $ r $ pointer may require $ O(n) $ updates to the $ k $ pointer, resulting in a total time complexity of $ O(n^{3 - 2x}) $.
-
When the $ l $ pointer moves to subsequent blocks:
The worst-case time complexity per movement is $ O(n) $. Assuming each block contributes once, the total time complexity is $ O(n^{1 - x}) $. Considering the impact of the $ k $ pointer, the total time complexity does not exceed $ O(n^{2 - x}) $.
Thus, the total time complexity for the $ k $ pointer does not exceed $ O(n^{\max(3 - 2x, 2 - x)}) $.
The worst-case time complexity for all three pointers is $ O(n^{\max(1, 3 - 2x, 2 - x)}) $. After mathematical analysis, it is found that $ x = \frac{2}{3} $ gives the optimal time complexity of $ O(n^{\frac{5}{3}}) $.
There is another way to write the modified Mo's algorithm with a block size of $ \sqrt[3]{nt} $, theoretically achieving an optimal complexity of $ O(\sqrt[3]{n^4t}) $.
Example
P1903 [National Training Team] Color Counting / Maintenance Queue
Classic problem.
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5e4;
const int maxq = 1e5 + 5e4;
const int maxv = 1e6 + 5;
int n, m, cur;
int l, r, k;
int qlen, clen;
int a[maxn], bel[maxn];
int cnt[maxv], ans[maxq];
struct ques
{
int l, r, k, id;
bool operator < (const ques& rhs) const
{
if (bel[l] ^ bel[rhs.l])
return bel[l] < bel[rhs.l];
if (bel[r] ^ bel[rhs.r])
return (bel[l] & 1 ? r < rhs.r : r > rhs.r);
return k < rhs.k;
}
} q[maxq];
struct node
{
int pos, color;
} c[maxq];
inline int read()
{
int res = 0, flag = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
flag = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
res = res * 10 + ch - '0';
ch = getchar();
}
return res * flag;
}
inline void write(int x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
inline void add(int x)
{
if (!cnt[a[x]])
cur++;
cnt[a[x]]++;
}
inline void del(int x)
{
cnt[a[x]]--;
if (!cnt[a[x]])
cur--;
}
inline void update(int x)
{
if (c[x].pos >= l && c[x].pos <= r)
{
if (!cnt[c[x].color])
cur++;
if (cnt[a[c[x].pos]] == 1)
cur--;
cnt[c[x].color]++;
cnt[a[c[x].pos]]--;
}
swap(c[x].color, a[c[x].pos]);
}
int main()
{
char ch;
n = read();
m = read();
int block = pow(n, 0.666);
for (register int i = 1; i <= n; i++)
{
a[i] = read();
bel[i] = (i - 1) / block + 1;
}
for (register int i = 1; i <= m; i++)
{
scanf(" %c ", &ch);
if (ch == 'Q')
{
qlen++;
q[qlen].l = read();
q[qlen].r = read();
q[qlen].id = qlen;
q[qlen].k = clen;
}
else
{
clen++;
c[clen].pos = read();
c[clen].color = read();
}
}
sort(q + 1, q + qlen + 1);
for (register int i = 1; i <= qlen; i++)
{
while (l < q[i].l)
del(l++);
while (l > q[i].l)
add(--l);
while (r < q[i].r)
add(++r);
while (r > q[i].r)
del(r--);
while (k < q[i].k)
update(++k);
while (k > q[i].k)
update(k--);
ans[q[i].id] = cur;
}
for (register int i = 1; i <= qlen; i++)
write(ans[i]), puts("");
return 0;
}
Rollback Mo's Algorithm
Concept
Assume there is a Mo's algorithm where one of the modification or deletion operations is difficult, while the other is simple.
Consider using a rollback Mo's algorithm to maintain this. Again, consider brute-force rollback and optimize complexity through proper sorting.
First, sort the queries based on the block number of the left endpoint as the primary key, and the right endpoint as the secondary key in ascending order.
Classify the queries by the block number of their left endpoint.
For queries in the same class, initialize the $ r $ pointer to the end of the block and the $ l $ pointer to the start of the next block.
For each query, if the $ r $ pointer is to the left of the current query's right endpoint, move the $ r $ pointer to the right.
Since these queries have their left endpoints in the same block, they are sorted by the right endpoint in ascending order, allowing reuse of the $ r $ pointer updates from the end of the block.
After updating, save the answer, denoted as $ k $.
A special case occurs when the left and right endpoints of a query are in the same block. In this case, the time complexity of the brute-force approach does not exceed $ O(\sqrt{n}) $, and it can be handled directly.
If the $ l $ pointer is to the right of the current query's left endpoint, move the $ l $ pointer to the current query's left endpoint and update the answer.
At this point, the answer for the query has been calculated. We also need to remove the influence of the left pointer and restore it to the start of the next block.
Repeat the above process for all queries in the same block, ensuring to clear the influence of the left pointer. The total time complexity does not exceed $ O(n\sqrt{n} + m\sqrt{n}) $.
Proof
Proof: Divide all queries into two categories. Let the number of queries with both endpoints in the same block be $ a $, and those with endpoints in different blocks be $ b $, with the total number of queries being $ m $.
For the first category of queries, the left and right pointers scan at most $ O(\sqrt{n}) $ positions each time, resulting in a total time complexity of $ O(a\sqrt{n}) $ for the first category.
For the second category of queries, further classify them by the block number of their left endpoint. Obviously, for each query, the left pointer scans at most $ \sqrt{n} $ positions.
Since the right endpoints of queries in the same block are sorted in ascending order, the right pointer scans at most $ n $ positions per block. There are at most $ \sqrt{n} $ such blocks, and the total length of the left pointer scans is at most $ b \times \sqrt{n} $, while the total length of the right pointer scans is at most $ \sqrt{n} \times n $. Adding these together gives a maximum of $ b \times \sqrt{n} + n \times \sqrt{n} $ positions scanned.
Adding the two categories to gether gives $ a\sqrt{n} + b\sqrt{n} + n\sqrt{n} $, resulting in a total time complexity of $ O(n\sqrt{n} + m\sqrt{n}) $.
Example
AT1219 Research on History
Classic problem, the difficulty lies in the large value range.
We find that when maintaining the frequency of occurrences, we only need the relative sizes, i.e., maintaining the frequency of the $ k $-th largest number.
Thus, consider using discretized arrays during the Mo's algorithm, and refer back to the original array when calculating values.
After discretization, maintain the frequency of each value, and update the answer when the frequency increases. See the code for details.
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
const int maxq = 1e5 + 5;
const int maxv = 1e5 + 5;
const int maxb = 1e3 + 5;
int n, m;
int l, r;
int st[maxb], ed[maxb];
int bel[maxn], cnt[maxv];
int a[maxn], b[maxn], c[maxn];
long long vis, cur;
long long ans[maxq];
struct ques
{
int l, r, id;
bool operator < (const ques& rhs) const
{
if (bel[l] ^ bel[rhs.l])
return bel[l] < bel[rhs.l];
return r < rhs.r;
}
} q[maxq];
inline int read()
{
int res = 0, flag = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
flag = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
res = res * 10 + ch - '0';
ch = getchar();
}
return res * flag;
}
inline void write(long long x)
{
if (x < 0)
{
x = -x;
putchar('-');
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
inline void add(int x)
{
cnt[a[x]]++;
cur = max(cur, (long long)cnt[a[x]] * b[a[x]]);
}
inline long long solve(int l, int r)
{
long long res = 0;
for (register int i = l; i <= r; i++)
c[a[i]] = 0;
for (register int i = l; i <= r; i++)
{
c[a[i]]++;
res = max(res, (long long)c[a[i]] * b[a[i]]);
}
return res;
}
int main()
{
int idx = 1;
n = read();
m = read();
int block = sqrt(n);
int size = ceil(n * 1.0 / block);
for (register int i = 1; i <= size; i++)
{
st[i] = (i - 1) * block + 1;
ed[i] = i * block;
}
for (register int i = 1; i <= n; i++)
{
a[i] = b[i] = read();
bel[i] = (i - 1) / block + 1;
}
for (register int i = 1; i <= m; i++)
{
q[i].l = read();
q[i].r = read();
q[i].id = i;
}
sort(q + 1, q + m + 1);
sort(b + 1, b + n + 1);
int len = unique(b + 1, b + n + 1) - b - 1;
for (register int i = 1; i <= n; i++)
a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
for (register int i = 1; i <= size; i++)
{
memset(cnt, 0, (n + 1) * sizeof(int));
cur = 0;
r = ed[i];
while (bel[q[idx].l] == i)
{
l = ed[i] + 1;
if (bel[q[idx].l] == bel[q[idx].r])
{
ans[q[idx].id] = solve(q[idx].l, q[idx].r);
idx++;
continue;
}
while (r < q[idx].r)
add(++r);
vis = cur;
while (l > q[idx].l)
add(--l);
ans[q[idx].id] = cur;
cur = vis;
while (l <= ed[i])
cnt[a[l++]]--;
idx++;
}
}
for (register int i = 1; i <= m; i++)
write(ans[i]), putchar('\n');
return 0;
}
Tree-based Mo's Algorithm
Concept
Use dfs order or Euler tour to flatten the tree into a sequence.
Example
SP10707 COT2 - Count on a Tree II
Consider flattening the Euler tour.
Let the first occurrence position of node $ i $ in the Euler tour be $ s_i $, and the last occurrence position be $ t_i $.
Suppose two nodes $ x, y $ satisfy $ s_x < s_y $, and the LCA of $ x, y $ is $ x $, indicating that $ y $ is a descendant of $ x $.
For the Euler tour interval $ [s_x, s_y] $, nodes that appear exactly once must be on the path from $ x $ to $ y $.
If $ LCA(x, y) \neq x $, it means $ x $ and $ y $ are in different subtrees. In this case, take the interval $ t_x, s_y $.
For the second case, the LCA might be missing. During the maintenance of Mo's algorithm, the LCA of $ x, y $ needs to be updated.
Note that the tree-based Mo's algorithm processes the Euler tour, so the bel array should handle $ 2n $ positions.
Code
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 4e4 + 5;
const int maxm = 1e5 + 5;
int n, m;
int tot, Cnt, cur;
int f[maxn][20], st[maxn], ed[maxn];
int cnt[maxn], ans[maxm], p[maxn * 2];
int head[maxn], dep[maxn], a[maxn], b[maxn], bel[maxn * 2];
bool vis[maxn * 2];
struct edge
{
int to, nxt;
} edge[2 * maxn];
struct ques
{
int l, r, lca, id;
bool operator < (const ques& rhs) const
{
if (bel[l] ^ bel[rhs.l])
return bel[l] < bel[rhs.l];
return (bel[l] & 1 ? r < rhs.r : r > rhs.r);
}
} q[maxm];
inline int read()
{
int res = 0, flag = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
flag = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
res = res * 10 + ch - '0';
ch = getchar();
}
return res * flag;
}
void add_edge(int u, int v)
{
Cnt++;
edge[Cnt].to = v;
edge[Cnt].nxt = head[u];
head[u] = Cnt;
}
void dfs(int u)
{
p[++tot] = u;
st[u] = tot;
dep[u] = dep[f[u][0]] + 1;
for (int i = head[u]; i; i = edge[i].nxt)
{
int v = edge[i].to;
if (v != f[u][0])
{
f[v][0] = u;
dfs(v);
}
}
p[++tot] = u;
ed[u] = tot;
}
void add(int x)
{
if (!vis[x])
{
if (!cnt[a[x]])
cur++;
cnt[a[x]]++;
}
else
{
cnt[a[x]]--;
if (!cnt[a[x]])
cur--;
}
vis[x] ^= 1;
}
int lca(int u, int v)
{
if (dep[u] < dep[v])
swap(u, v);
int k = 0;
while ((1 << (k + 1)) <= n)
k++;
for (int i = k; i >= 0; i--)
if (dep[f[u][i]] >= dep[v])
u = f[u][i];
if (u == v)
return u;
for (int i = k; i >= 0; i--)
{
if (f[u][i] != f[v][i])
{
u = f[u][i];
v = f[v][i];
}
}
return f[u][0];
}
int main()
{
int u, v, x;
int l = 1, r = 0;
n = read();
m = read();
for (int i = 1; i <= n; i++)
a[i] = b[i] = read();
for (int i = 1; i <= n - 1; i++)
{
u = read();
v = read();
add_edge(u, v);
add_edge(v, u);
}
sort(b + 1, b + n + 1);
int len = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; i++)
a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
int block = sqrt(n);
for (int i = 1; i <= 2 * n; i++)
bel[i] = (i - 1) / block + 1;
dfs(1);
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i <= n; i++)
f[i][j] = f[f[i][j - 1]][j - 1];
for (int i = 1; i <= m; i++)
{
u = read();
v = read();
if (st[u] >= st[v])
swap(u, v);
x = lca(u, v);
q[i].id = i;
if (x == u)
{
q[i].l = st[u];
q[i].r = st[v];
}
else
{
q[i].l = ed[u];
q[i].r = st[v];
q[i].lca = x;
}
}
sort(q + 1, q + m + 1);
for (int i = 1; i <= m; i++)
{
while (l < q[i].l)
add(p[l++]);
while (l > q[i].l)
add(p[--l]);
while (r < q[i].r)
add(p[++r]);
while (r > q[i].r)
add(p[r--]);
if (q[i].lca)
add(q[i].lca);
ans[q[i].id] = cur;
if (q[i].lca)
add(q[i].lca);
}
for (int i = 1; i <= m; i++)
printf("%d\n", ans[i]);
return 0;
}
Optimization
Odd-Even Optimization
If the block numbers of the left endpoints differ, sort by the block number of the left endpoint. Otherwise, if the block number of the left endpoint is odd, sort by the right endpoint in ascending order, otherwise in descending order. This can theoretically reduce the constant factor by up to $ \frac{1}{2} $.
bool operator < (const ques& rhs) const
{
if (bel[l] ^ bel[rhs.l])
return bel[l] < bel[rhs.l];
return (bel[l] & 1 ? r < rhs.r : r > rhs.r);
}
Mo's Algorithm with Two Passes
Mo's algorithm with two passes is used when the contribution of moving endpoints cannot be transferred in $ O(1) $.
Consider re-offline the movement operations of Mo's algorithm to simplify the problem.
The information to be maintained must be additive and subtractive.
Example: P4887 [Template] Mo's Algorithm with Two Passes (Fourteenth Block)
Let $ f(x, [l, r]) $ be the contribution of position $ x $ to the inetrval $ [l, r] $.
Consider the cases of moving the endpoints:
- Moving the left endpoint left, $ [l, r] \rightarrow [l - k, r] $, the contribution increases by $ \sum_{i = l - k}^{l - 1} f(i, [1, r]) - f(i, [1, i - 1]) $
- Moving the left endpoint right, $ [l, r] \rightarrow [l + k, r] $, the contribution decreases by $ \sum_{i = l}^{l + k - 1} f(i, [1, r]) - f(i, [1, i - 1]) $
- Moving the right endpoint left, $ [l, r] \rightarrow [l, r - k] $, the contribution decreases by $ \sum_{i = r - k + 1}^{r} f(i, [1, i - 1]) - f(i, [1, l - 1]) $
- Moving the right endpoint right, $ [l, r] \rightarrow [l, r + k] $, the contribution increases by $ \sum_{i = r + 1}^{r + k} f(i, [1, i - 1]) - f(i, [1, l - 1]) $
Take the last case as an example, consider how to maintain the two sides of the expression.
The left side $ f(i, [1, i - 1]) $ can be preprocessed.
For the right side $ f(i, [1, l - 1]) $, it actually represents the total contribution of the prefix up to $ l - 1 $ with $ i $, which can be maintained by scanning forward.
That is, attach a query for the interval $ [r + 1, r + k] $ at position $ l - 1 $, asking for the total contribution of this interval with $ [1, l - 1] $. Since $ k \leq \sqrt{n} $, it can be directly scanned.
Specifically, for this problem, simply use a bucket to count.
Time complexity $ O({n \choose 17}n + n \sqrt{m}) $
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
namespace IO
{
//by cyffff
int len = 0;
char ibuf[(1 << 20) + 1], *iS, *iT, out[(1 << 26) + 1];
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#define reg register
inline int read()
{
reg char ch = gh();
reg int x = 0;
reg char t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gh();
return t ? -x : x;
}
inline void putc(char ch) { out[len++] = ch; }
template<class T>
inline void write(T x)
{
if (x < 0) putc('-'), x = -x;
if (x > 9) write(x / 10);
out[len++] = x % 10 + 48;
}
inline void flush()
{
fwrite(out, 1, len, stdout);
len = 0;
}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::putc;
const int maxn = 1e5 + 5;
const int maxm = 1e5 + 5;
const int maxv = (1 << 14);
int n, m, k;
int buc[maxv];
int a[maxn], bel[maxn], pre[maxn];
ll ans[maxm];
vector<int> num;
struct Query
{
int l, r, idx;
ll ans;
Query() : l(), r(), idx(), ans() {}
Query(int _l, int _r, int _idx) : l(_l), r(_r), idx(_idx), ans() {}
bool operator < (const Query& rhs) const { return (bel[l] == bel[rhs.l] ? r < rhs.r : l < rhs.l); }
} qry[maxn];
vector<Query> opt[maxn];
int main()
{
// freopen("P4887_13.in", "r", stdin);
// freopen("P4887_13.res", "w", stdout);
n = read(), m = read(), k = read();
if (k > 14)
{
while (m--) puts("0");
return 0;
}
int blk = sqrt(n);
for (int i = 1; i <= n; i++) bel[i] = (i - 1) / blk + 1, a[i] = read();
for (int i = 1; i <= m; i++) qry[i].idx = i, qry[i].l = read(), qry[i].r = read();
sort(qry + 1, qry + m + 1);
for (int i = 0; i < maxv; i++)
if (__builtin_popcount(i) == k) num.push_back(i);
for (int i = 1; i <= n; i++)
{
for (int v : num) buc[a[i] ^ v]++;
pre[i] = buc[a[i + 1]];
}
for (int i = 1, l = 1, r = 0; i <= m; i++)
{
if (l < qry[i].l) opt[r].push_back(Query(l, qry[i].l - 1, -i));
while (l < qry[i].l) qry[i].ans += pre[l - 1], l++;
if (l > qry[i].l) opt[r].push_back(Query(qry[i].l, l - 1, i));
while (l > qry[i].l) qry[i].ans -= pre[l - 2], l--;
if (r < qry[i].r) opt[l - 1].push_back(Query(r + 1, qry[i].r, -i));
while (r < qry[i].r) qry[i].ans += pre[r], r++;
if (r > qry[i].r) opt[l - 1].push_back(Query(qry[i].r + 1, r, i));
while (r > qry[i].r) qry[i].ans -= pre[r - 1], r--;
}
memset(buc, 0, sizeof(buc));
for (int i = 1; i <= n; i++)
{
for (int v : num) buc[a[i] ^ v]++;
for (Query x : opt[i])
{
for (int j = x.l, tmp; j <= x.r; j++)
{
tmp = buc[a[j]];
if ((j <= i) && (k == 0)) tmp--;
if (x.idx < 0) qry[-x.idx].ans -= tmp;
else qry[x.idx].ans += tmp;
}
}
}
for (int i = 1; i <= m; i++) qry[i].ans += qry[i - 1].ans, ans[qry[i].idx] = qry[i].ans;
for (int i = 1; i <= m; i++) write(ans[i]), putc('\n');
flush();
return 0;
}
From lxl's cutting-edge Mo's algorithm technology.
To optimize the complexity of Mo's algorithm to $ \mathcal{O}(n \sqrt{q}) $, you only need to change the block size to $ \frac{n}{\sqrt{q}} $.