分块算法，和莫队有着异曲同工之妙，是一种优雅的暴力。
概述
分块算法，顾名思义是把一个长度为 $n$ 的序列分成 $m$ 块，每块的大小均为 $\frac{n}{m}$。我们维护块内信息，使得块内信息的查询是 $\mathcal O(1)$ 的，而总的询问又可以看做是若干个块的询问的总和。
为了方便描述，我们定义：
- 完整块：区间操作时，完整包含于区间的块。
- 不完整的块：区间操作时，只有部分包含于区间的块，即左右端点所在的两个块。
- 零散元素：不完整的块内的元素。
我们发现，对于一个询问 $[l, r]$，我们可以进行如下处理：
- 拆成若干个完整块，其中每个完整快内的信息可以 $\mathcal O(1)$ 更新。其中完整块的数量为 $\mathcal O(\frac{n}{m})$。
- 剩下两个不完整的块，对于这两个块内的信息暴力更新。其中不完整的块的大小为 $\mathcal O(m)$。
综上所述，分块算法单次操作的时间复杂度为 $\mathcal O(\frac{n}{m}+m)$。根据均值不等式，我们可以发现 $m=\sqrt n$ 时复杂度最优。
如何分块
我们定义如下变量：
| $len$ | $num$ | $bl[i]$ | $l[i]$ | $r[i]$ |
|---|---|---|---|---|
| 块的大小 | 块的数量 | 第 $i$ 个元素所属的块 | 第 $i$ 个块的左端点 | 第 $i$ 个块的右端点 |
那么我们可以用如下代码建立分块：
其中特别需要注意 r[num] = n 意味着第 $num$ 个块（最后一个块）的右端点一定是 $n$！void build() {
len = sqrt(n), num = (n - 1) / len + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / len + 1;
}
for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * len + 1, r[i] = i * len;
}
r[num] = n;
}接下来我们就用 $9$ 个来自 LOJ 的例题（可能稍有修改）来简单讲解一下分块的思想。
例题 1
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法，单点求值。
Solution
我们用 $tag[i]$ 记录第 $i$ 个块内每个元素都加的值。
对于修改操作 $[x, y]$ 有两种情况：
- 其中 $x$ 和 $y$ 在同一个块内，那么直接暴力修改 $a[i]$ 的值即可。
- 其中 $x$ 和 $y$ 不在同一个块内，那么先修改整块 $(bl[x], bl[y])$ 的 $tag$ 值，然后再对 $x$ 和 $y$ 所在的块内的零散元素暴力修改 $a[i]$ 的值。
对于查询操作 $x$，直接输出 $a[x] + tag[bl[x]]$ 的值。
时间复杂度：$\mathcal O(m\sqrt n)$
Code
#include <cstdio>
#include <cmath>
const int N = 1e5 + 5, M = 320;
int n, m, len, num, a[N], bl[N], l[M], r[M], tag[M];
void build() {
len = sqrt(n), num = (n - 1) / len + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / len + 1;
}
for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * len + 1, r[i] = i * len;
}
r[num] = n;
}
void modify(int x, int y, int v) {
if (bl[x] == bl[y]) {
for (int i = x; i <= y; i++) a[i] += v;
} else {
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) tag[i] += v;
for (int i = x; i <= r[bl[x]]; i++) a[i] += v;
for (int i = l[bl[y]]; i <= y; i++) a[i] += v;
}
}
int query(int x) {
return a[x] + tag[bl[x]];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build();
for (int i = 1; i <= m; i++) {
int opt;
scanf("%d", &opt);
if(!opt) {
int x, y, v;
scanf("%d%d%d", &x, &y, &v);
modify(x, y, v);
} else {
int x;
scanf("%d", &x);
printf("%d\n", query(x));
}
}
return 0;
}例题 2
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法，区间查询小于 $v$ 的元素个数。
Solution
我们首先考虑没有修改操作怎么做：
- 对于零散元素，我们直接暴力查找。
- 对于整块，我们可以先排序然后直接二分查找。
如果有了修改操作，那么意味着我们每次修改后需要重新排序，还是分成两部分考察：
- 对于零散元素，我们暴力修改后对不完整块直接重新排序。时间复杂度为 $\mathcal O(\sqrt n\log n)$。
- 对于整块，我们发现修改不影响元素之间的相对顺序，所以不需要排序。查询时需要用 $v - tag[i]$ 的值二分查找。时间复杂度为 $\mathcal O(\sqrt n)$。
时间复杂度：$\mathcal O(m\sqrt n\log n)$（其中可以用均值不等式计算出更优的复杂度 QAQ）
Code
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
const int N = 1e5 + 5, M = 320;
int n, m, len, num, a[N], bl[N], l[M], r[M], tag[M];
std::vector<int> ve[M];
void build() {
len = sqrt(n), num = (n - 1) / len + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / len + 1;
ve[bl[i]].push_back(a[i]);
}
for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * len + 1, r[i] = i * len;
std::sort(ve[i].begin(), ve[i].end());
}
r[num] = n;
}
void reset(int x) {
ve[x].clear();
for (int i = l[x]; i <= r[x]; i++) ve[x].push_back(a[i]);
std::sort(ve[x].begin(), ve[x].end());
}
void modify(int x, int y, int v) {
if (bl[x] == bl[y]) {
for (int i = x; i <= y; i++) a[i] += v;
reset(bl[x]);
} else {
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) tag[i] += v;
for (int i = x; i <= r[bl[x]]; i++) a[i] += v;
for (int i = l[bl[y]]; i <= y; i++) a[i] += v;
reset(bl[x]), reset(bl[y]);
}
}
int query(int x, int y, int v) {
int ans = 0;
if (bl[x] == bl[y]) {
for (int i = x; i <= y; i++) {
if (a[i] + tag[bl[i]] < v) ans++;
}
} else {
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) {
ans += std::lower_bound(ve[i].begin(), ve[i].end(), v - tag[i]) - ve[i].begin();
}
for (int i = x; i <= r[bl[x]]; i++) {
if (a[i] + tag[bl[i]] < v) ans++;
}
for (int i = l[bl[y]]; i <= y; i++) {
if (a[i] + tag[bl[i]] < v) ans++;
}
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build();
for (int i = 1; i <= m; i++) {
int opt, x, y, v;
scanf("%d%d%d%d", &opt, &x, &y, &v);
if(!opt) {
modify(x, y, v);
} else {
printf("%d\n", query(x, y, v));
}
}
return 0;
}例题 3
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法，区间查询 $v$ 的前驱。
Solution
我们有一个很直观的想法：直接沿用例题 2 的思路，只要修改一下二分即可。
但是这题有一个更简单的方法，直接用 $\text{set}$ 维护块内信息。这样甚至可以支持插入和删除操作，更加方便。但是 $\text{set}$ 常数巨大，所以此题不建议使用 $\text{set}$ 来维护。
时间复杂度：$\mathcal O(m\sqrt n\log n)$
Code
直接二分查找
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
const int N = 1e5 + 5, M = 320;
int n, m, len, num, a[N], bl[N], l[M], r[M], tag[M];
std::vector<int> ve[M];
void build() {
len = sqrt(n), num = (n - 1) / len + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / len + 1;
ve[bl[i]].push_back(a[i]);
}
for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * len + 1, r[i] = i * len;
std::sort(ve[i].begin(), ve[i].end());
}
r[num] = n;
}
void reset(int x) {
ve[x].clear();
for (int i = l[x]; i <= r[x]; i++) ve[x].push_back(a[i]);
std::sort(ve[x].begin(), ve[x].end());
}
void modify(int x, int y, int v) {
if (bl[x] == bl[y]) {
for (int i = x; i <= y; i++) a[i] += v;
reset(bl[x]);
} else {
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) tag[i] += v;
for (int i = x; i <= r[bl[x]]; i++) a[i] += v;
for (int i = l[bl[y]]; i <= y; i++) a[i] += v;
reset(bl[x]), reset(bl[y]);
}
}
int query(int x, int y, int v) {
int ans = -1;
if (bl[x] == bl[y]) {
for (int i = x; i <= y; i++) {
int val = a[i] + tag[bl[i]];
if (val < v) ans = std::max(ans, val);
}
} else {
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) {
std::vector<int>::iterator it = std::lower_bound(ve[i].begin(), ve[i].end(), v - tag[i]);
if (it != ve[i].begin()) ans = std::max(ans, *(--it) + tag[i]);
}
for (int i = x; i <= r[bl[x]]; i++) {
int val = a[i] + tag[bl[i]];
if (val < v) ans = std::max(ans, val);
}
for (int i = l[bl[y]]; i <= y; i++) {
int val = a[i] + tag[bl[i]];
if (val < v) ans = std::max(ans, val);
}
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
build();
for (int i = 1; i <= m; i++) {
int opt, x, y, v;
scanf("%d%d%d%d", &opt, &x, &y, &v);
if(!opt) {
modify(x, y, v);
} else {
printf("%d\n", query(x, y, v));
}
}
return 0;
}使用 $\text{set}$ 维护
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
const int N = 1e5 + 5, M = 320;
int n, m, len, num, a[N], bl[N], l[M], r[M], tag[M];
std::set<int> s[M];
void build() {
len = sqrt(n), num = (n - 1) / len + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / len + 1;
s[bl[i]].insert(a[i]);
}
for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * len + 1, r[i] = i * len;
}
r[num] = n;
}
void update(int x, int v) {
s[bl[x]].erase(a[x]), s[bl[x]].insert(a[x] += v);
}
void modify(int x, int y, int v) {
if (bl[x] == bl[y]) {
for (int i = x; i <= y; i++) update(i, v);
} else {
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) tag[i] += v;
for (int i = x; i <= r[bl[x]]; i++) update(i, v);
for (int i = l[bl[y]]; i <= y; i++) update(i, v);
}
}
int query(int x, int y, int v) {
int ans = -1;
if (bl[x] == bl[y]) {
for (int i = x; i <= y; i++) {
int val = a[i] + tag[bl[i]];
if (val < v) ans = std::max(ans, val);
}
} else {
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) {
std::set<int>::iterator it = s[i].lower_bound(v - tag[i]);
if (it != s[i].begin()) ans = std::max(ans, *(--it) + tag[i]);
}
for (int i = x; i <= r[bl[x]]; i++) {
int val = a[i] + tag[bl[i]];
if (val < v) ans = std::max(ans, val);
}
for (int i = l[bl[y]]; i <= y; i++) {
int val = a[i] + tag[bl[i]];
if (val < v) ans = std::max(ans, val);
}
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build();
for (int i = 1; i <= m; i++) {
int opt, x, y, v;
scanf("%d%d%d%d", &opt, &x, &y, &v);
if(!opt) {
modify(x, y, v);
} else {
printf("%d\n", query(x, y, v));
}
}
return 0;
}例题 4
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法，区间求和。答案对 $10^9 + 7$ 取模。
Solution
这题还是和例题 1 一样的思路，只不过需要多维护一个区间和：我们定义 $sum[i]$ 表示第 $i$ 个块的总和（不包括 $tag[i]$ 的值，也就是说这两者是独立的）。
我们先分析修改操作，对于两种情况分类讨论：
- 对于零散元素，我们暴力修改 $a[i]$ 和 $sum[bl[i]]$ 的值。
- 对于整块，只需要修改 $tag[i]$ 的值即可，而不需要修改 $sum[i]$ 的值。
我们再分析查询操作，对于两种情况分类讨论：
- 对于零散元素，我们用 $a[i] + tag[bl[i]]$ 来更新答案。
对于整块，经过简单的思考就可以发现答案就是 $sum[i] + tag[i]\times len$ 的总和。
为什么可以直接用 $len$ 的值？因为我们在统计时，只使用 $(bl[x], bl[y])$ 这个闭区间内的整块，不涉及最后一个块，所以每个块的大小必为 $len$。
时间复杂度：$\mathcal O(m\sqrt n)$
Code
#include <cstdio>
#include <cmath>
const int N = 1e5 + 5, M = 320;
const int mod = 1e9 + 7;
int n, m, len, num, a[N], bl[N], l[M], r[M], tag[M], sum[M];
void add(int &x, int y) {
(x += y) >= mod && (x -= mod);
}
void build() {
len = sqrt(n), num = (n - 1) / len + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / len + 1;
add(sum[bl[i]], a[i]);
}
for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * len + 1, r[i] = i * len;
}
r[num] = n;
}
void modify(int x, int y, int v) {
if (bl[x] == bl[y]) {
for (int i = x; i <= y; i++) a[i] += v;
add(sum[bl[x]], 1LL * (y - x + 1) * v % mod);
} else {
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) add(tag[i], v);
for (int i = x; i <= r[bl[x]]; i++) add(a[i], v);
add(sum[bl[x]], 1LL * (r[bl[x]] - x + 1) * v % mod);
for (int i = l[bl[y]]; i <= y; i++) add(a[i], v);
add(sum[bl[y]], 1LL * (y - l[bl[y]] + 1) * v % mod);
}
}
int query(int x, int y) {
int ans = 0;
if (bl[x] == bl[y]) {
for (int i = x; i <= y; i++) add(ans, a[i]);
add(ans, 1LL * (y - x + 1) * tag[bl[x]] % mod);
} else {
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) {
add(ans, sum[i]);
add(ans, 1LL * tag[i] * len % mod);
}
for (int i = x; i <= r[bl[x]]; i++) add(ans, a[i]);
add(ans, 1LL * (r[bl[x]] - x + 1) * tag[bl[x]] % mod);
for (int i = l[bl[y]]; i <= y; i++) add(ans, a[i]);
add(ans, 1LL * (y - l[bl[y]] + 1) * tag[bl[y]] % mod);
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build();
for (int i = 1; i <= m; i++) {
int opt, x, y;
scanf("%d%d%d", &opt, &x, &y);
if(!opt) {
int v;
scanf("%d", &v);
modify(x, y, v);
} else {
printf("%d\n", query(x, y));
}
}
return 0;
}例题 5
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间开方，区间求和。
Solution
由于有区间开方操作，没法直接更新区间和，问题貌似比较棘手。
但是我们可以分析一下开方的性质：一个 $10^9$ 的数字不断进行开方，其值大约为：$10^9, 31622, 177, 13, 3, 1, 1, 1, \cdots$
那么意味着，每个数最多被开方大约 $5$ 次，这样我们可以记录每个块中是否有 $>1$ 的元素。如果没有则不需要对这个块内元素开方操作。
有了这个性质，直接暴力操作即可。
时间复杂度：$\mathcal O(m\sqrt n)$
Code
#include <cstdio>
#include <cmath>
const int N = 1e5 + 5, M = 320;
int n, m, len, num, a[N], bl[N], l[M], r[M], sum[M];
bool flg[M];
void build() {
len = sqrt(n), num = (n - 1) / len + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / len + 1;
sum[bl[i]] += a[i];
}
for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * len + 1, r[i] = i * len;
}
r[num] = n;
}
void solve(int x) {
if (flg[x]) return;
sum[x] = 0, flg[x] = 1;
for (int i = l[x]; i <= r[x]; i++) {
sum[x] += (a[i] = sqrt(a[i]));
flg[x] &= (a[i] <= 1);
}
}
void modify(int x, int y) {
if (bl[x] == bl[y]) {
for (int i = x; i <= y; i++) {
sum[bl[x]] -= a[i];
sum[bl[x]] += (a[i] = sqrt(a[i]));
}
} else {
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) solve(i);
for (int i = x; i <= r[bl[x]]; i++) {
sum[bl[x]] -= a[i];
sum[bl[x]] += (a[i] = sqrt(a[i]));
}
for (int i = l[bl[y]]; i <= y; i++) {
sum[bl[y]] -= a[i];
sum[bl[y]] += (a[i] = sqrt(a[i]));
}
}
}
int query(int x, int y) {
int ans = 0;
if (bl[x] == bl[y]) {
for (int i = x; i <= y; i++) ans += a[i];
} else {
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) ans += sum[i];
for (int i = x; i <= r[bl[x]]; i++) ans += a[i];
for (int i = l[bl[y]]; i <= y; i++) ans += a[i];
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
build();
for (int i = 1; i <= m; i++) {
int opt, x, y;
scanf("%d%d%d", &opt, &x, &y);
if(!opt) {
modify(x, y);
} else {
printf("%d\n", query(x, y));
}
}
return 0;
}例题 6
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持单点插入，单点求值。
Solution
首先考虑数据随机的情况，那么每个块内插入的操作是均摊的。我们只需要用 $\text{vector}$ 维护每个块，暴力插入查询即可，时间复杂度依旧为 $\mathcal O(m\sqrt n)$。
我们发现，在极限数据下，某个块内可能会被插入至多 $\mathcal O(m)$ 次，这样单次操作的复杂度就变成了 $\mathcal O(m)$，显然是不能接受的。
我们发现，当一个块的大小过大时就会影响整体的复杂度。那么我们在块过大时进行重构分块，我们定义一个阈值 $k$，当某个块的大小超过 $k\times len$ 时，我们对整个序列进行重构。一般而言，这个阈值 $k$ 在 $20$ 左右复杂度较优。
当然还有一个方法：每进行 $\sqrt n$ 次插入操作后就进行重构。每次重构的复杂度为 $\mathcal O(n + m)$，那么总体的复杂度还是 $\mathcal O(m\sqrt n)$（默认 $n$ 和 $m$ 同阶）。
时间复杂度：$\mathcal O(m\sqrt n)$
Code
#include <cstdio>
#include <cmath>
#include <vector>
const int N = 1e5 + 5, M = 500;
int n, m, len, num, a[N], st[N << 1];
std::vector<int> ve[M];
void build() {
len = sqrt(n), num = (n - 1) / len + 1;
for (int i = 1; i <= n; i++) {
ve[(i - 1) / len + 1].push_back(a[i]);
}
}
void rebuild() {
int top = 0;
for (int i = 1; i <= num; i++) {
for (int j = 0; j < (int)ve[i].size(); j++) {
st[++top] = ve[i][j];
}
ve[i].clear();
}
len = sqrt(top), num = (top - 1) / len + 1;
for (int i = 1; i <= top; i++) {
ve[(i - 1) / len + 1].push_back(st[i]);
}
}
std::pair<int, int> get(int k) {
int x = 1;
while (k > (int)ve[x].size()) k -= ve[x++].size();
return std::make_pair(x, k - 1);
}
void insert(int x, int v) {
std::pair<int, int> r = get(x);
int i = r.first;
ve[i].insert(ve[i].begin() + r.second, v);
if ((int)ve[i].size() > 20 * len) rebuild();
}
int query(int x) {
std::pair<int, int> r = get(x);
return ve[r.first][r.second];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build();
for (int i = 1; i <= m; i++) {
int opt, x;
scanf("%d%d", &opt, &x);
if(!opt) {
int v;
scanf("%d", &v);
insert(x, v);
} else {
printf("%d\n", query(x));
}
}
return 0;
}例题 7
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间乘法，区间加法，单点求值。答案对 $10007$ 取模。
Solution
我们发现修改操作和「Luogu 3373」【模板】线段树 2 的套路非常相似。
首先我们强制乘法比加法优先。也就是说，块内维护两个标记 $add[i]$ 和 $mul[i]$ 分别表示整个块内加、乘的值。一个元素 $a[i]$ 实际表示的值为 $a[i]\times mul[bl[i]]+add[bl[i]]$。
- 块内乘法 $v$：假如两个标记的值为 $A$ 和 $M$，那么标记变成 $A\times v$ 和 $M\times v$。
- 块内加法 $v$：假如两个标记的值为 $A$ 和 $M$，那么标记变成 $A + v$ 和 $M$。
对于零散元素，我们无法直接修改，所以直接暴力将所在块内的标记转移到元素上，然后将标记清空（$add[i] = 0, mul[i] = 1$），直接对零散元素本身修改即可。
时间复杂度：$\mathcal O(m \log n)$。
Code
#include <cstdio>
#include <cmath>
const int N = 1e5 + 5, M = 320;
const int mod = 10007;
int n, m, len, num, a[N], bl[N], l[M], r[M], add[M], mul[M];
void build() {
len = sqrt(n), num = (n - 1) / len + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / len + 1;
}
for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * len + 1, r[i] = i * len, mul[i] = 1;
}
r[num] = n;
}
void add(int &x, int y) {
(x += y) >= mod && (x-=mod);
}
void reset(int x) {
for (int i = l[x]; i <= r[x]; i++) {
a[i] = (a[i] * mul[x] + add[x]) % mod;
}
add[x] = 0, mul[x] = 1;
}
void modifyAdd(int x, int y, int v) {
if (bl[x] == bl[y]) {
reset(bl[x]);
for (int i = x; i <= y; i++) add(a[i], v);
} else {
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) add(add[i], v);
reset(bl[x]), reset(bl[y]);
for (int i = x; i <= r[bl[x]]; i++) add(a[i], v);
for (int i = l[bl[y]]; i <= y; i++) add(a[i], v);
}
}
void modifyMul(int x, int y, int v) {
if (bl[x] == bl[y]) {
reset(bl[x]);
for (int i = x; i <= y; i++) (a[i] *= v) %= mod;
} else {
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) {
(add[i] *= v) %= mod, (mul[i] *= v) %= mod;
}
reset(bl[x]), reset(bl[y]);
for (int i = x; i <= r[bl[x]]; i++) (a[i] *= v) %= mod;
for (int i = l[bl[y]]; i <= y; i++) (a[i] *= v) %= mod;
}
}
int query(int x) {
return (a[x] * mul[bl[x]] + add[bl[x]]) % mod;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build();
for (int i = 1; i <= m; i++) {
int opt;
scanf("%d", &opt);
if(!opt) {
int x, y, v;
scanf("%d%d%d", &x, &y, &v);
modifyAdd(x, y, v % mod);
} else if (opt == 1) {
int x, y, v;
scanf("%d%d%d", &x, &y, &v);
modifyMul(x, y, v % mod);
} else {
int x;
scanf("%d", &x);
printf("%d\n", query(x));
}
}
return 0;
}例题 8
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间查询等于 $v$ 的元素个数并覆盖为 $v$。
Solution
我们先考虑一个暴力的做法，对于修改操作：
- 对于零散元素，我们暴力修改。注意单点修改前需要下放标记！
- 对于整块，我们对这个块打上标记，表示整个块内的元素相同，均为 $v$。
然后考虑查询操作：
- 对于零散元素，我们下放标记后暴力查询。
- 对于整块，如果这个块内有标记且标记的值为 $v$，那么对答案有 $len$ 的贡献。如果没有标记，那么我们对 $[l[i], r[i]]$ 区间内的元素暴力查询。
这个做法看上去单次查询的复杂度为 $\mathcal O(n)$，但是我们这样分析：
假设初始序列都是同一个值，那么单次查询的复杂度为 $\mathcal O(\sqrt n)$。如果这是进行一个区间操作，它最多破环首位 $2$ 个块的标记，所以只能使得后面的询问至多增加 $2$ 个块的暴力时间，所以均摊的单次复杂度为 $\mathcal O(\sqrt n)$。
换句话说，要让一次操作耗费 $\mathcal O(n)$ 的时间，要先花费 $\mathcal O(\sqrt n)$ 个操作对数列进行修改！综上所述，总体时间复杂度为 $\mathcal O(m\sqrt n)$。
时间复杂度：$\mathcal O(m\sqrt n)$
Code
#include <cstdio>
#include <cmath>
const int N = 1e5 + 5, M = 320;
int n, m, len, num, a[N], bl[N], l[M], r[M], cov[M];
bool tag[M];
void build() {
len = sqrt(n), num = (n - 1) / len + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / len + 1;
}
for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * len + 1, r[i] = i * len;
}
r[num] = n;
}
void reset(int x) {
if(!tag[x]) return;
for (int i = l[x]; i <= r[x]; i++) a[i] = cov[x];
tag[x] = 0;
}
void modify(int x, int y, int v) {
if (bl[x] == bl[y]) {
reset(bl[x]);
for (int i = x; i <= y; i++) a[i] = v;
} else {
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) {
tag[i] = 1, cov[i] = v;
}
reset(bl[x]), reset(bl[y]);
for (int i = x; i <= r[bl[x]]; i++) a[i] = v;
for (int i = l[bl[y]]; i <= y; i++) a[i] = v;
}
}
int query(int x, int y, int v) {
int ans = 0;
if (bl[x] == bl[y]) {
reset(bl[x]);
for (int i = x; i <= y; i++) ans += (a[i] == v);
} else {
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) {
if (tag[i]) {
ans += (cov[i] == v ? len : 0);
} else {
for (int j = l[i]; j <= r[i]; j++) ans += (a[j] == v);
}
}
reset(bl[x]), reset(bl[y]);
for (int i = x; i <= r[bl[x]]; i++) ans += (a[i] == v);
for (int i = l[bl[y]]; i <= y; i++) ans += (a[i] == v);
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build();
for (int i = 1; i <= m; i++) {
int x, y, v;
scanf("%d%d%d", &x, &y, &v);
printf("%d\n", query(x, y, v));
modify(x, y, v);
}
return 0;
}例题 9
给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间查询最小众数。
Solution
以下解法中，我们为了方便表述，定义 $\text{mode}(i)$ 表示第 $i$ 个整块的众数。
解法 1（无修改）
我们首先可以发现一个性质：对于询问 $[x, y]$，答案 $\in\text{mode}(i\sim j)\cup\text{零散元素}$（其中 $\text{mode}(i\sim j$) 表示 $[x, y]$ 内的所有整块的众数）。令 $l, r$ 分别在第 $a, b$ 块，那么 $[l, r]$ 可以拆成：
- 从 $l$ 到第 $a$ 块的最后一个元素。
- 从第 $a + 1$ 块到第 $b - 1$ 块。
- 从第 $b$ 块的起始一个元素到 $r$。
根据这个性质，我们只需要至多比较 $2\sqrt n + 1$ 即 $\mathcal O(\sqrt n)$ 个数的出现次数即可。
那么我们可以 $\mathcal O(n\sqrt n)$ 预处理 $f[i][j]$ 表示第 $i$ 个整块到第 $j$ 个整块的众数。然后对于每个种值开一个 $\text{vector}$ 记录值 $i$ 出现的位置。
接下来考虑询问 $[x, y]$ 怎么分解处理：
- 对于零散元素，我们暴力查找每个元素在 $[x, y]$ 内的出现次数，这个过程可以通过在记录 $a[i]$ 出现位置的 $ve[a[i]]$ 内二分查找实现。
- 对于整块，众数为 $f[bl[x] + 1][bl[y] - 1]$，出现次数同理可以二分得到。
我们只需要在这 $\mathcal O(\sqrt n)$ 个数内找到出现次数最多的数即可。
注意，为了方便计算需要事先对数据离散化。
时间复杂度：$\mathcal O(m\sqrt n\log n)$，可以通过均值不等式计算出块的大小为 $\sqrt{\frac{n}{\log n}}$ 以获得更优的复杂度通过本题。
期望得分：$80\sim 100$
解法 2（无修改）
我们考虑在解法 1 的基础上进行修改。首先 $\sqrt n$ 这个系数是肯定没法去掉了，考虑如何仍然在 $\sqrt n$ 分块下去掉 $\log n$ 这个系数。这意味着我们要在 $\mathcal O(1)$ 的时间内回答询问。
不妨设 $F[i][x]$ 表示 $[0, i]$ 之间有多少个 $x$。那么 $[l, r]$ 之间的 $x$ 的数量就是 $F[r][x] - F[l - 1][x]$，所以可以省去一个二分的 $\log n$。
预处理时，我们只需要对序列扫一遍即可，复杂度为 $\mathcal O(n)$。
时间复杂度：$\mathcal O(m\sqrt n)$
期望得分：$100$
解法 3（带修改）
貌似可以 $\sqrt[3] n$ 分块？推荐阅读 区间众数解题报告 - 陈立杰 改日填坑
Code
解法 1
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
const int N = 1e5 + 5, M = 1300;
int n, m, len, num, a[N], val[N], bl[N], l[M], r[M], cnt[N], f[M][M];
std::vector<int> p[N];
void build() {
for (int i = 1; i <= n; i++) val[i] = a[i];
std::sort(val + 1, val + n + 1);
int sz = std::unique(val + 1, val + n + 1) - (val + 1);
for (int i = 1; i <= n; i++) {
a[i] = std::lower_bound(val + 1, val + sz + 1, a[i]) - val;
p[a[i]].push_back(i);
}
len = sqrt(n / log2(n)), num = (n - 1) / len + 1;
for (int i = 1; i <= n; i++) {
bl[i] = (i - 1) / len + 1;
}
for (int i = 1; i <= num; i++) {
l[i] = (i - 1) * len + 1, r[i] = i * len;
}
r[num] = n;
}
void init() {
for (int i = 1; i <= num; i++) {
memset(cnt, 0, sizeof(cnt));
int ans = 0, mx = 0;
for (int j = i; j <= num; j++) {
for (int k = l[j]; k <= r[j]; k++) {
cnt[a[k]]++;
if (cnt[a[k]] > mx || (cnt[a[k]] == mx && a[k] < ans)) {
ans = a[k], mx = cnt[a[k]];
}
}
f[i][j] = ans;
}
}
}
int sum(int l, int r, int v) {
return std::upper_bound(p[v].begin(), p[v].end(), r) - std::lower_bound(p[v].begin(), p[v].end(), l);
}
void solve(int x, int y, int l, int r, int &ans, int &mx) {
for (int i = x; i <= y; i++) {
int now = sum(l, r, a[i]);
if (now > mx || (now == mx && a[i] < ans)) {
ans = a[i], mx = now;
}
}
}
int query(int x, int y) {
int ans = 0, mx = 0;
if (bl[x] + 1 >= bl[y]) {
solve(x, y, x, y, ans, mx);
} else {
ans = f[bl[x] + 1][bl[y] - 1], mx = sum(x, y, ans);
solve(x, r[bl[x]], x, y, ans, mx);
solve(l[bl[y]], y, x, y, ans, mx);
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build(), init();
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", val[query(x, y)]);
}
return 0;
}解法 2
// 改日填坑解法 3
// 改日填坑习题
- Ynoi 吼啊！
4 条评论
我是 Siyuan，我 AK IOI
qaq
Orz
Orz！！！！