分块

万能算法

分块就是把一组数据分成一个个小的块,在处理时对于被完全包含了的块,直接读取块中的信息,而对于块外的直接暴力即可。一般来说,块的大小为sqrt(n)。

准确的说分块只是一种思想,而不是一种算法。因此,我们直接在题目中对分块进行讲解。

接下来我们来看一道分块入门题目:洛谷 P4168 [Violet]蒲公英

这道题虽然题面很长,但是就只是让你求了一个众数。众所周知,只有简单的题才需要延长题面来干扰你做题,因此这道题非常简单。我们只需要维护每个块内的众数,然后枚举块外的数,判断他们在当前区间中的数是否超过了块内的答案,然后更新即可。还有一些细节操作见代码:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m, x, len, k, cnt;
int a[40005], b[40005], pos[40005], num[40005];
int l[205], r[205], f[205][205], w[205][40005];
int query(int lx, int rx)
{
int ans = -1, ll = lx, rr = rx;
if (pos[lx] == pos[rx])
{
for (int i = lx; i <= rx; ++i)
num[a[i]] = 0;
for (int i = lx; i <= rx; ++i)
{
++num[a[i]];
if (ans == -1 || num[a[i]] > num[ans] || (num[a[i]] == num[ans] && a[i] < ans))
ans = a[i];
}
return ans;
}
while (lx != l[pos[lx]])
++lx;
while (rx != r[pos[rx]])
--rx;
if (pos[lx] <= pos[rx])
{
ans = f[pos[lx]][pos[rx]];
num[ans] = w[pos[rx]][ans] - w[pos[lx] - 1][ans];
}
for (int i = ll; i <= lx - 1; ++i)
num[a[i]] = w[pos[rx]][a[i]] - w[pos[lx] - 1][a[i]];
for (int i = rx + 1; i <= rr; ++i)
num[a[i]] = w[pos[rx]][a[i]] - w[pos[lx] - 1][a[i]];
--lx;
++rx;
for (int i = ll; i <= lx; ++i)
{
++num[a[i]];
if (ans == -1 || num[a[i]] > num[ans] || (num[a[i]] == num[ans] && a[i] < ans))
ans = a[i];
}
for (int i = rx; i <= rr; ++i)
{
++num[a[i]];
if (ans == -1 || num[a[i]] > num[ans] || (num[a[i]] == num[ans] && a[i] < ans))
ans = a[i];
}
return ans;
}
int main()
{
scanf("%d%d", &n, &m);
k = sqrt(n);
for (int i = 1; i <= n; i += k)
{
++cnt;
l[cnt] = i;
r[cnt] = min(n, i + k - 1);
for (int j = i; j <= min(n, i + k - 1); ++j)
pos[j] = cnt;
}
for (int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
b[i] = a[i];
}
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;
for (int i = 1; i <= cnt; ++i)
{
for (int j = 1; j <= n; ++j)
w[i][a[j]] = w[i - 1][a[j]];
for (int j = l[i]; j <= r[i]; ++j)
{
++w[i][a[j]];
if (f[i][i] == -1 || w[i][a[j]] - w[i - 1][a[j]] > w[i][f[i][i]] - w[i - 1][f[i][i]] || (w[i][a[j]] - w[i - 1][a[j]] == w[i][f[i][i]] - w[i - 1][f[i][i]] && a[j] < f[i][i]))
f[i][i] = a[j];
}
}
for (int i = 1; i <= cnt; ++i)
for (int j = i + 1; j <= cnt; ++j)
{
f[i][j] = f[i][j - 1];
for (int k = l[j]; k <= r[j]; ++k)
if (w[j][a[k]] - w[i - 1][a[k]] > w[j][f[i][j]] - w[i - 1][f[i][j]] || (w[j][a[k]] - w[i - 1][a[k]] == w[j][f[i][j]] - w[i - 1][f[i][j]] && a[k] < f[i][j]))
f[i][j] = a[k];
}
for (int i = 1; i <= m; ++i)
{
int lx, rx;
scanf("%d%d", &lx, &rx);
lx = (lx + x - 1) % n + 1;
rx = (rx + x - 1) % n + 1;
if (lx > rx)
swap(lx, rx);
x = b[query(lx, rx)];
printf("%d\n", x);
}
return 0;
}

看吧,分块就是这么简单。接下来你所有题目的复杂度都会带根号了。

评论

此博客中的热门博文