分块莫队学习笔记

优雅的暴力。

引入

link。
这道题显然可以用线段树、树状数组做，但如果我偏不用这些数据结构呢？
我们知道，暴力修改和查询最坏是 \(\mathcal{O}(n)\) 的，这样肯定会挂掉。
那该怎么办呢？
正题

分块

考虑将序列分成若干块，我们设每块长为 \(B\)。
对于每次查询 \(\left [ l, r \right ]\)，我们涉及到修改的块是 \(\left [ b_l, b_r \right ]\)（\(b_i\) 代表 \(i\) 属于哪个块）。
其中 \(\left [ b_l + 1, b_r - 1 \right ]\) 是整块都被修改了。
不妨设置一个懒标记，把每块的整块操作都加到这里面。
这样修改的复杂度是 \(\mathcal{O}(\frac{n}{B})\) 的。
那剩下的我们就可以暴力操作，复杂度是 \(\mathcal{O}(B)\) 的。
查询同理。
此时修改查询的复杂度就变成了 \(\mathcal{O}(B + \frac{n}{B})\) 了。
使得该数最小的显然是 \(B = \sqrt{n}\)，所以该算法的时间复杂度是 \(\mathcal{O}(m\sqrt{n})\)。
分块主要解决区修区查类问题，只要满足以下条件即可：

• 可以打懒标记（结合律）。
  
• 时间复杂度允许。
  

优势：可解决问题范围广。
劣势：时间复杂度高。
时间复杂度：\(\mathcal{O}(m\sqrt{n})\)。
空间复杂度：\(\mathcal{O}(n)\)。
莫队

普通莫队

莫队是一种离线算法，需要满足以下条件：

• 在知道 \(\left [ l, r \right ]\) 的答案的情况下，可以 \(\mathcal{O}(1)\) 求出  \(\left [ l, r + 1 \right ]\)、 \(\left [ l, r - 1 \right ]\)、 \(\left [ l + 1, r \right ]\)、 \(\left [ l - 1, r \right ]\) 的答案。
  
• 允许离线。
  
• 只有询问没有修改。
  

首先将所有的询问离线下来，记为  \(\left [ ql_1, qr_1 \right ],\left [ ql_2, qr_2 \right ],\dots,\left [ ql_m, qr_m \right ]\)。
将询问排序（这正是莫队算法的精髓），从上一个询问的答案一个个改到当前询问，得到答案。
实现：

1. for (int i = 1; i <= m; i++) {
2.         while (l < q[i].l) del(l++);
3.         while (r > q[i].r) del(r--);
4.         while (l > q[i].l) add(--l);
5.         while (r < q[i].r) add(++r);
6.         ans[q[i].id] = res;
7. }

复制代码

但是仔细分析发现时间复杂度仍然可以被卡成 \(nm\)，一点都不优秀，甚至会更慢。
考虑优化。
我们想要优化复杂度的根本是让 \(l\) 和 \(r\) 指针移动的距离尽量少。
对询问范围进行分块，块长为 \(B\)。
以询问左端点的块编号为第一关键字，右端点为第二关键字排序。

• 如果当前询问与上一次处于同一块，则 \(l\) 最多移动 \(B\)。
  
• 不同块的询问，\(l\) 最多移动 \(2B\)。
  

则：

• \(l\) 移动的复杂度是 \(m\times B = mB\)；
  
• \(r\) 的复杂度是 \(\frac{n}{B} \times n = \frac{n^2}{B}\)。
  

则复杂度是 \(\mathcal{O}(mB + \frac{n^2}{B})\)。
使得该式最小的 \(B\) 的值是 \(\frac{n}{\sqrt m}\)，则此时的时间复杂度就是 \(\mathcal{O}(n\sqrt{m} + m\log m)\)。
\(m \log m\) 是排序的复杂度。
总结一下。
普通莫队解决的问题满足以下条件：

• 在知道 \(\left [ l, r \right ]\) 的答案的情况下，可以 \(\mathcal{O}(1)\) 求出  \(\left [ l, r + 1 \right ]\)、 \(\left [ l, r - 1 \right ]\)、 \(\left [ l + 1, r \right ]\)、 \(\left [ l - 1, r \right ]\) 的答案。
  
• 允许离线。
  
• 只有询问没有修改。
  

优势：再没有更快的思维做法之前，她几乎是跑得最快并且思维含量最低的。
劣势：只支持离线。
时间复杂度： \(\mathcal{O}(n\sqrt{m} + m\log m)\)。
空间复杂度： \(\mathcal{O}(n)\)。
例题 1：小 B 的询问

非常板子的一道，维护一下 \(c\) 数组即可。
[code]#include // #define int long long#define pii pair#define FRE(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout)#define ALL(x) x.begin(), x.end()using namespace std;int _test_ = 1;const int N = 50008;int n, m, k, block_size, res, cnt[N], a[N], ans[N];struct node {        int l, r, id;} q[N];bool operator> n >> m >> k;        for (int i = 1; i > a;        }        block_size = n / sqrt(m); // 块长        for (int i = 1; i > q.l >> q.r;                q.id = i;        }        sort(q + 1, q + m + 1);        int l = 1, r = 0;        for (int i = 1; i  q.r) del(r--);                while (l > q.l) add(--l);                while (r < q.r) add(++r);                ans[q.id] = res;        }        for (int i = 1; i  n >> m;        for (int i = 1; i > a;        }        block_size = n / sqrt(m);        for (int i = 1; i > q.l >> q.r;                q.id = i;        }        sort(q + 1, q + m + 1);        int l = 1, r = 0;        for (int i = 1; i  q.r) del(r--);                while (l > q.l) add(--l);                while (r < q.r) add(++r);                if (res.first == 0) {                        ans[q.id] = {0, 1};                        continue;                }                int g = __gcd(res.first, res.second);                ans[q.id] = {res.first / g, res.second / g};        }        for (int i = 1; i > l >> r;                if (op == 'Q') q[++cnt_q] = {l, r, cnt_c, cnt_q};                else c[++cnt_c] = {l, r, 0, 0};        }        sort(q + 1, q + cnt_q + 1);        int l = 1, r = 0, t = 0;        for (int i = 1; i  q.l) add(a[--l]);                while (r < q.r) add(a[++r]);                while (l < q.l) del(a[l++]);                while (r > q.r) del(a[r--]);                while (t < q.t) upt(++t, i);                while (t > q.t) upt(t--, i);                 ans[q.id] = res;        }        for (int i = 1; i