「BZOJ 3809」Gty 的二逼妹子序列 - 莫队 + 分块

发表于 | 分类于

给一个序列，每次求 之间权值在 之间的不同的数的数量。

链接

BZOJ 3809

题解

莫队，用一个数据结构维护前缀和，维护当前区间每个数的出现次数，某个数第一次出现时在数据结构中加上这个数，最后一次删除时在数据结构中将其删除，每次转移到目标区间后在数据结构中查询两个前缀和作差。

这个数据结构可以用分块维护，分别维护每个位置的值和每个块的值，修改时分别在目标位置和所在块的值上加上增量，复杂度 ，查询时将整块的和整块外的值分别加入，复杂度 。因为只需要进行 次查询，所以这部分的时间复杂度为 ，并且转移时的复杂度相对与树状数组等结构少一个 。

代码

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

const int MAXN = 100000;
const int MAXN_SQRT = 317 + 10; // Math.sqrt(100000) = 316.22776601683796
const int MAXM = 1000000;

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

struct Query {
    int l, r, a, b, *ans;

    bool operator<(const Query &other) const
    {
        if (l / blockSize == other.l / blockSize) return (l / blockSize % 2 == 1) ? (r < other.r) : (r > other.r);
        else return l / blockSize < other.l / blockSize;
    }
} Q[MAXM + 1];

struct Blocklize {
    int blockSize, blockCnt, valBlock[MAXN_SQRT + 1], val[MAXN + 1];

    void init(int n)
    {
        blockSize = ceil(sqrt(n));
        blockCnt = n / blockSize + (n % blockSize != 0);
    }

    int whichBlock(int x)
    {
        return (x - 1) / blockSize + 1;
    }

    int getBlockL(int bid)
    {
        return (bid - 1) * blockSize + 1;
    }

    int query(int pos)
    {
        int bid = whichBlock(pos), ans = 0;
        for (int i = 1; i < bid; i++) ans += valBlock[i];
        for (int i = getBlockL(bid); i <= pos; i++) ans += val[i];
        return ans;
    }

    void update(int pos, int delta)
    {
        int bid = whichBlock(pos);
        valBlock[bid] += delta;
        val[pos] += delta;
    }
} ds; // data structure

inline void extend(int pos, int d)
{
    int x = a[pos];
    if (d == 1)
    {
        if (++cnt[x] == 1) ds.update(x, d);
    }
    else
    {
        if (--cnt[x] == 0) ds.update(x, d);
    }
}

inline int query(int a, int b)
{
    return ds.query(b) - ds.query(a - 1);
}

inline void mo()
{
    int l = 1, r = 0;
    for (int i = 1; i <= m; i++)
    {
        Query &q = Q[i];
        while (r < q.r) extend(++r, 1);
        while (r > q.r) extend(r--, -1);
        while (l > q.l) extend(--l, 1);
        while (l < q.l) extend(l++, -1);

        *q.ans = query(q.a, q.b);
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    blockSize = ceil(sqrt(n));
    ds.init(n);

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

    static int ans[MAXM + 1];
    for (int i = 1; i <= m; i++)
    {
        scanf("%d %d %d %d", &Q[i].l, &Q[i].r, &Q[i].a, &Q[i].b);
        Q[i].ans = &ans[i];
    }

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

    mo();

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