「BZOJ 2724」蒲公英 - 分块

给一个长度为 的序列，每次查询一个区间 内的众数（如果有多个众数，取最小的一个），强制在线。

链接

BZOJ 2724

题解

离散化，将序列分为 块，维护 表示第 块到第 块之间的答案， 表示 这个数在前 个块中的出现次数。

每次查询，对于中间完整的块，取出其答案。对于两边不是完整的块的部分，遍历一遍求出其出现次数，加上这些数在中间块的出现次数（由前缀和得到），并尝试更新答案。

代码

#include <cstdio>
// #include <cstring>
// #include <cassert>
#include <cmath>
#include <algorithm>

const int MAXN = 40000;
const int MAXN_SQRT = 200;
const int MAXM = 50000;

// 离散化用到的 set（集合）和 tot（不重复的数字数量）
int n, a[MAXN + 1], set[MAXN + 1], tot;
// 块大小、块数量、cnt[x][i] 表示 x 这个数在前 i 个块中的出现次数，ans[l][r] 表示第 l 个块到第 r 个块的答案
int blockSize, blockCnt, cnt[MAXN + 1][MAXN_SQRT + 1], ans[MAXN_SQRT + 1][MAXN_SQRT + 1];

// 离散化
inline void discrete()
{
    std::copy(a + 1, a + n + 1, set + 1);
    std::sort(set + 1, set + n + 1);
    int *end = std::unique(set + 1, set + n + 1);
    for (int i = 1; i <= n; i++) a[i] = std::lower_bound(set + 1, end, a[i]) - set;

    tot = end - (set + 1); // 区间 [set + 1, end) 的长度
}

// 给一个位置，求所在块编号
inline int blockID(int i)
{
    return (i - 1) / blockSize + 1;
}

// 给一个块编号，求其区间
inline void blockInterval(int i, int &l, int &r)
{
    l = (i - 1) * blockSize + 1;
    r = i * blockSize;

    // 防止越界
    r = std::min(r, n);
}

// 预处理
inline void prepare()
{
    // 以根号 n 分块
    blockSize = ceil(sqrt(n));
    blockCnt = blockID(n);

    // cnt[x][i] 表示 x 这个数在第 i 个块中的出现次数
    for (int i = 1; i <= n; i++)
    {
        int bi = blockID(i);
        cnt[a[i]][bi]++;
    }

    // 做前缀和
    for (int i = 1; i <= blockCnt; i++)
    {
        for (int j = 1; j <= tot; j++) cnt[j][i] += cnt[j][i - 1];
    }

    // 求 ans[l][r]
    for (int i = 1; i <= blockCnt; i++)
    {
        // cnt[x] 表示 x 这个数在第 [i, j] 这个块区间内的出现次数
        static int cnt[MAXN + 1];
        std::fill(cnt + 1, cnt + tot + 1, 0); // 清空 cnt

        int tmp = 0; // 表示当前答案
        for (int j = i; j <= blockCnt; j++) // j 从 i 开始枚举，每次向后扩充一个块
        {
            // 将第 j 个块加入到答案中
            int l, r;
            blockInterval(j, l, r);

            // 枚举第 j 个块的所有数
            for (int k = l; k <= r; k++)
            {
                cnt[a[k]]++;

                // 更新答案
                // 注意，根据题意，出现次数相同时取较小值
                if (!tmp || cnt[a[k]] > cnt[tmp] || (cnt[a[k]] == cnt[tmp] && a[k] < tmp)) tmp = a[k];
            }

            // 记录答案
            ans[i][j] = tmp;
        }
    }
}

// 暴力计算 [l, r] 的答案
inline int force(int l, int r)
{
    static int cnt[MAXN + 1];

    int ans = 0;
    for (int i = l; i <= r; i++)
    {
        cnt[a[i]]++;

        // 更新答案
        if (!ans || cnt[a[i]] > cnt[ans] || (cnt[a[i]] == cnt[ans] && a[i] < ans)) ans = a[i];
    }

    // 清空 cnt，注意不能 memset 或者 std::fill
    // 因为我们需要 force() 的时间复杂度与 [l, r] 的区间长度有关，与序列中总数的数量无关
    for (int i = l; i <= r; i++) cnt[a[i]]--;

    return ans;
}

// 计算 a 中的 n 个数的答案（这些数是在查询时不在块内的数）
// 统计数的出现次数时，额外加入每个数在 [lb, rb] 这些（完整的）块内的出现次数
// 并将新答案与旧答案 oldAns 取较优
inline int calcPart(int lb, int rb, int *a, int n, int &oldAns, int &oldAnsCnt)
{
    static int cnt[MAXN + 1];

    // 加入这些数在块内的出现次数
    for (int i = 1; i <= n; i++)
    {
        cnt[a[i]] = ::cnt[a[i]][rb] - ::cnt[a[i]][lb - 1]; // 注意不能是 +=，因为数可能重复，避免重复加入
    }

    for (int i = 1; i <= n; i++)
    {
        cnt[a[i]]++; // 统计出现次数
    }

    int ans = oldAns, ansCnt = oldAnsCnt;
    for (int i = 1; i <= n; i++)
    {
        int newCnt = cnt[a[i]];

        // 更新答案
        if (!ans || newCnt > ansCnt || (newCnt == ansCnt && a[i] < ans))
        {
            ans = a[i];
            ansCnt = newCnt;
        }
    }

    // 清空 cnt
    for (int i = 1; i <= n; i++)
    {
        cnt[a[i]] = 0;
    }

    return ans;
}

// 求块 [lb, rb] 内的答案
inline void blockAns(int lb, int rb, int &ans, int &ansCnt)
{
    ans = ::ans[lb][rb];
    ansCnt = cnt[ans][rb] - cnt[ans][lb - 1]; // 前缀和作差
}

// 查询 [l, r] 间的答案
inline int query(int l, int r)
{
    int lb = blockID(l), rb = blockID(r);
    if (lb == rb || lb + 1 == rb) // 如果两端点在同一块或相邻块，则暴力计算
    {
        return force(l, r);
    }

    // 先计算块内的部分
    int ans, ansCnt;
    // [lb + 1, rb - 1] 是完整的块，lb 和 rb 不是完整的块
    blockAns(lb + 1, rb - 1, ans, ansCnt);

    // 取出块之外的数
    int cnt = 0; // 块之外的数的数量
    static int tmp[MAXN + 1]; // 块之外的数

    int ll, lr;
    blockInterval(lb, ll, lr);
    // 左半边块之外的
    for (int i = l; i <= lr; i++) tmp[++cnt] = a[i];

    int rl, rr;
    blockInterval(rb, rl, rr);
    // 右半边块之外的
    for (int i = rl; i <= r; i++) tmp[++cnt] = a[i];

    // 计算块外的部分，更新答案
    // [lb + 1, rb - 1] 是完整的块
    return calcPart(lb + 1, rb - 1, tmp, cnt, ans, ansCnt);
}

int main()
{
    int m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    discrete();
    prepare();

    int lastAns = 0; // 上一次的答案
    while (m--)
    {
        int l, r;
        scanf("%d %d", &l, &r);

        // 强制在线
        l = (l + lastAns - 1) % n + 1;
        r = (r + lastAns - 1) % n + 1;

        if (l > r) std::swap(l, r);

        // 将离散化后的值对应到原值
        printf("%d\n", lastAns = set[query(l, r)]);
    }

    return 0;
}