「SDOI2009」HH 的项链 - 莫队

给一个长度为 n 的序列,每次查询一个区间中不同的数的个数。

链接

BZOJ 1878

题解

莫队模板题。

代码

#include <cstdio>
#include <cmath>
#include <algorithm>

const int MAXN = 50000;
const int MAXM = 200000;
const int MAXX = 1000000;

int n, m, blockSize, a[MAXN + 1], cnt[MAXX + 1];

struct Query
{
    int l, r, *ans;

    // 以左端点所在块为第一关键字,右端点为第二关键字
    bool operator<(const Query &other) const
    {
        if (l / blockSize == other.l / blockSize) return r < other.r;
        else return l / blockSize < other.l / blockSize;
    }
} Q[MAXM + 1];

// extend - 莫队扩展的通用写法
// 对于 [l, r] 这段区间,要把左端点(left = true)还是
// 右端点(left = false)加入(d = 1)答案或从答案中删去(d = -1)
inline int extend(int l, int r, bool left, int d)
{
    if (left)
    {
        if (d == 1)
        {
            if (++cnt[a[l]] == 1) return 1;
            else return 0;
        }
        else
        {
            if (--cnt[a[l]] == 0) return -1;
            else return 0;
        }
    }
    else
    {
        if (d == 1)
        {
            if (++cnt[a[r]] == 1) return 1;
            else return 0;
        }
        else
        {
            if (--cnt[a[r]] == 0) return -1;
            else return 0;
        }
    }
}

// 莫队主过程
inline void solve()
{
    // 因为先扩展右端点,所以第一次一定是 r 变为 1,变成一个合法区间的答案
    int l = 1, r = 0, ans = 0; // ans 表示当前 [l, r] 区间的答案
    for (int i = 1; i <= m; i++)
    {
        const Query &q = Q[i];

        // 扩展右端点
        while (r < q.r) ans += extend(l, ++r, false, 1);
        while (r > q.r) ans += extend(l, r--, false, -1);

        // 扩展左端点
        while (l > q.l) ans += extend(--l, r, true, 1);
        while (l < q.l) ans += extend(l++, r, true, -1);

        // 记录答案
        // 将 ans 写入到 q.ans 指向的变量中
        *q.ans = ans;
    }
}

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

    // 求块大小 sqrt(n)
    blockSize = ceil(sqrt(n));

    scanf("%d", &m);
    // 记录答案的数组
    // 因为询问被排序,而要根据原顺序输出
    static int ans[MAXM + 1];
    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d", &Q[i].l, &Q[i].r);
        Q[i].ans = &ans[i]; // 无论怎么排序,第 i 个询问的答案要存到 ans[i] 里
    }

    std::sort(Q + 1, Q + m + 1);
    solve();

    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
}

精简版:

#include <cstdio>
#include <cmath>
#include <algorithm>

const int MAXN = 50000;
const int MAXM = 200000;
const int MAXX = 1000000;

int n, m, blockSize, a[MAXN + 1], cnt[MAXX + 1];

struct Query
{
    int l, r, *ans;

    // 以左端点所在块为第一关键字,右端点为第二关键字
    bool operator<(const Query &other) const
    {
        if (l / blockSize == other.l / blockSize) return r < other.r;
        else return l / blockSize < other.l / blockSize;
    }
} Q[MAXM + 1];

// extend - 本题莫队扩展的精简写法
// 把 x 这个数加入答案(d = 1)或从答案中删去(d = -1)
inline int extend(int x, int d)
{
    if (d == 1)
    {
        return ++cnt[x] == 1 ? 1 : 0; // 如果加入一个 x 后,x 的出现次数为 1,说明 x 首次出现,答案 +1
    }
    else
    {
        return --cnt[x] == 0 ? -1 : 0; // 如果删去一个 x 后,x 的出现次数为 0,说明原有的 x 全部被删除,答案 -1
    }
}

// 莫队主过程
inline void solve()
{
    // 因为先扩展右端点,所以第一次一定是 r 变为 1,变成一个合法区间的答案
    int l = 1, r = 0, ans = 0; // ans 表示当前 [l, r] 区间的答案
    for (int i = 1; i <= m; i++)
    {
        const Query &q = Q[i];

        // 扩展右端点
        while (r < q.r) ans += extend(a[++r], 1);
        while (r > q.r) ans += extend(a[r--], -1);

        // 扩展左端点
        while (l > q.l) ans += extend(a[--l], 1);
        while (l < q.l) ans += extend(a[l++], -1);

        // 记录答案
        // 将 ans 写入到 q.ans 指向的变量中
        *q.ans = ans;
    }
}

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

    // 求块大小 sqrt(n)
    blockSize = ceil(sqrt(n));

    scanf("%d", &m);
    // 记录答案的数组
    // 因为询问被排序,而要根据原顺序输出
    static int ans[MAXM + 1];
    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d", &Q[i].l, &Q[i].r);
        Q[i].ans = &ans[i]; // 无论怎么排序,第 i 个询问的答案要存到 ans[i] 里
    }

    std::sort(Q + 1, Q + m + 1);
    solve();

    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
}