分块——以poj3468和洛谷P4168为例

本文主要是介绍分块——以poj3468和洛谷P4168为例，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

当我们遇到简单的区间问题时，一般会想到树状数组或者线段树。但是当区间信息不符合区间可加可减性时，我们就要另寻他路了。这时我们可以选择用分块来解决问题。

分块要将你要处理的区间划分成长度大致相等的几块。为什么是大致相等呢？因为最后一个剩下的区间长度是难以控制的，剩下来的长度我们就让它自己成为一个区间，大概是这个样子。在这里插入图片描述
对于分块来说，我们要先记录下每个区间的左右极限，以及每个点所在的区间，比如点 $1$ 在第一个区间，点 $5$ 在第二个区间，之后在进行区间处理的时候，访问它们所在的区间。对于刚开始的信息还要进行预处理。

如果它们在一个区间内，例如点 $1$ 和点 $3$ ，那我们直接去遍历点 $1$ 到点 $3$ 即可
如果它们之间隔了几个区间，例如点 $2$ 和点 $7$ ，那么对于点 $2$ 和点 $7$ 所在的区间，我们按照上一条的方法，遍历点 $2$ 到点 $2$ 所在区间的右极限，遍历点 $7$ 所在区间的左极限到点 $7$ 。对于它们之间的区间，我们就对整个区间进行操作。

我们以poj3468为例。这是一道很常规的线段树区间更新，区间求和的板子题。我们将区间以 $\sqrt{n}$ 为长度划分，用分块写出来大概是这样的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;typedef long long ll;
const int maxn = 1e5 + 7;int l[maxn], r[maxn], pos[maxn];
ll sum[maxn], a[maxn], c, lazy[maxn];
int n, m, t, ql, qr;
char op[1];
void add(int ql, int qr, ll c) {int pl = pos[ql], pr = pos[qr];if (pl == pr) {for (int i = ql; i <= qr; ++i) {a[i] += c;}sum[pl] += c * (qr - ql + 1);return;}for (int i = ql; i <= r[pl]; ++i) {a[i] += c;}sum[pl] += c * (r[pl] - ql + 1);for (int i = l[pr]; i <= qr; ++i) {a[i] += c;}sum[pr] += c * (qr - l[pr] + 1);for (int i = pl + 1; i < pr; ++i) {lazy[i] += c;}
}ll query(int ql, int qr) {int pl = pos[ql], pr = pos[qr];ll res = 0;//应注意对于边边角角的点也要加上lazy值if (pl == pr) {for (int i = ql; i <= qr; ++i) {res += a[i] + lazy[pl];}return res;}for (int i = ql; i <= r[pl]; ++i) res += a[i] + lazy[pl];for (int i = l[pr]; i <= qr; ++i) res += a[i] + lazy[pr];for (int i = pl + 1; i < pr; ++i) res += sum[i] + lazy[i] * (r[i] - l[i] + 1);return res;
}
int main() {scanf("%d %d", &n, &m);for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);int t = sqrt(n);for (int i = 1; i <= t; ++i) {l[i] = (i - 1) * t + 1;r[i] = i * t;}if (n > t * t) {l[t + 1] = t * t + 1;r[t + 1] = n;t++;}for (int i = 1; i <= t; ++i) {for (int j = l[i]; j <= r[i]; ++j) {pos[j] = i;sum[i] += a[j];}}while (m--) {scanf("%s %d %d", op, &ql, &qr);if (op[0] == 'Q') {printf("%lld\n", query(ql, qr));}else {scanf("%lld", &c);add(ql, qr, c);}}return 0;
}

到这里可能还会觉得分块没有什么用，在代码量和时间复杂度上都不如别的数据结构。但是如果我们遇到了洛谷P4168这类型的题目，就无法简单地用线段树和树状数组去处理。

它要求输出区间出现次数最多的数，如果有多个这样的数，则输出最小的，并且强制在线。区间众数不满足区间相加，所以我们采用分块来写。我们现在还不能确定分块要分多少块，这里先设为 $T$ 。由于这道题目的数值很大，我们采取离散化处理。离散化之后，我们先确定好各点所在的区间，然后预处理 $n u m [i] [j]$ ，代表某个区间到某个区间的编号是 $i$ ，其中第 $j$ 个颜色出现了多少次，并用 $r e s$ 数组来记录当前区间的答案，总共有 $T^2$ 个区间。这样预处理之后，我们在进行访问的时候，就可以直接得到中间一段块的信息，就只用处理边边角角的数据。同时应该注意到，若访问的是处于同一区间的点，或者是相邻区间的点，都要进行遍历。

然后我们发现预处理需要 $O(T^2N)$ ，分块的长度是 $N / T$ ，所以我们 $M$ 次询问需要 $O (M N / T)$ 。我们令 $T^2N = MN/T$ ， $M$ 和 $N$ 为同一个数量级，可得 $T$ 为 $\sqrt[3]{N}$ 。所以确定了 $T$ 的大小。

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int maxn = 4e4 + 7;int num[1000][maxn];
int l[maxn], r[maxn], pos[maxn], res[1000], ma[1000];
int cor[maxn], a[maxn], cnt[1000][maxn], c[maxn];
int n, m, t, ql, qr, len, tot;
int query(int ql, int qr) {int ans, maxx = 0;int pl = pos[ql], pr = pos[qr];if (pr - pl <= 1) {for (int i = ql; i <= qr; ++i) {c[cor[i]]++;if (c[cor[i]] > maxx) maxx = c[cor[i]], ans = cor[i];else if (c[cor[i]] == maxx && cor[i] < ans) ans = cor[i];}for (int i = ql; i <= qr; ++i) c[cor[i]]--;return ans;}ans = res[cnt[pl + 1][pr - 1]];maxx = ma[cnt[pl + 1][pr - 1]];for (int i = ql; i <= r[pl]; ++i) {c[cor[i]]++;if (c[cor[i]] + num[cnt[pl + 1][pr - 1]][cor[i]] > maxx) {maxx = c[cor[i]] + num[cnt[pl + 1][pr - 1]][cor[i]];ans = cor[i];}else if (c[cor[i]] + num[cnt[pl + 1][pr - 1]][cor[i]] == maxx) {if (cor[i] < ans) ans = cor[i];}}for (int i = l[pr]; i <= qr; ++i) {c[cor[i]]++;if (c[cor[i]] + num[cnt[pl + 1][pr - 1]][cor[i]] > maxx) {maxx = c[cor[i]] + num[cnt[pl + 1][pr - 1]][cor[i]];ans = cor[i];}else if (c[cor[i]] + num[cnt[pl + 1][pr - 1]][cor[i]] == maxx) {if (cor[i] < ans) ans = cor[i];}}for (int i = ql; i <= r[pl]; ++i) c[cor[i]]--;for (int i = l[pr]; i <= qr; ++i) c[cor[i]]--;return ans;
}
int main() {scanf("%d %d", &n, &m);t = pow(n, 1.0 / 3);len = n / t;for (int i = 1; i <= n; ++i)  scanf("%d", &cor[i]), a[i] = cor[i];for (int i = 1; i <= t; ++i) {l[i] = r[i - 1] + 1;r[i] = i * len;}if (n > r[t]) {t++;l[t] = r[t - 1] + 1;r[t] = n;}for (int i = 1; i <= n; ++i) {for (int j = l[i]; j <= r[i]; ++j) pos[j] = i;}sort(a + 1, a + 1 + n);tot = unique(a + 1, a + 1 + n) - a - 1;for (int i = 1; i <= n; ++i) {cor[i] = lower_bound(a + 1, a + 1 + tot, cor[i]) - a;}int now = 0;for (int i = 1; i <= t; ++i) {int L = l[i];for (int j = i; j <= t; ++j) {int R = r[j];cnt[i][j] = ++now;int maxx = 0;for (int k = L; k <= R; ++k) {num[cnt[i][j]][cor[k]]++;if (num[cnt[i][j]][cor[k]] > maxx) {maxx = num[cnt[i][j]][cor[k]];res[cnt[i][j]] = cor[k];ma[cnt[i][j]] = maxx;}else if (num[cnt[i][j]][cor[k]] == maxx && cor[k] < res[cnt[i][j]]) res[cnt[i][j]] = cor[k];}}}int pre = 0;while (m--) {scanf("%d %d", &ql, &qr);ql = ((ql + pre - 1) % n) + 1, qr = ((qr + pre - 1) % n) + 1;if (ql > qr) swap(ql, qr);pre = a[query(ql, qr)];printf("%d\n", pre);}return 0;
}