分块

万能算法

分块就是把一组数据分成一个个小的块，在处理时对于被完全包含了的块，直接读取块中的信息，而对于块外的直接暴力即可。一般来说，块的大小为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;
}

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