首页 > 编程语言 >莫队算法

莫队算法

时间：2023-01-02 15:46:42浏览次数：63  
标签：cnt int res BlockId Add -- 算法 莫队

概念

莫队算法是由莫涛提出的算法，可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。

假设 \(n=m\) ，对于序列上的区间询问问题，如果得知 \([l,r]\) 的答案，可以在 \(O(1)\) 的时间推算出 \([l-1,r],[l+1,r],[l,r-1],[l,r+1]\) 的答案，那么我们就可以在 \(O(n\sqrt{n})\) 的时间求出所有询问的答案。

实现

将所有的询问离线后以左端点所在的块为第一关键字，右端点为第二关键字进行排序。按排序后的顺序处理每一个询问，暴力从上一个区间的答案推出当前区间的答案。

核心代码：

for (int i = 1; i <= m; ++i) {
    while (l < q[i].l)
        Del(l++);

    while (l > q[i].l)
        Add(--l);

    while (r < q[i].r)
        Add(++r);

    while (r > q[i].r)
        Del(r--);

    ans[q[i].AnsId] = res;
}

优化

在很多时候，我们不能盲目的将块长设置为 \(\sqrt{n}\)​​ ，如果遇到 \(m\)​​ 和 \(\sqrt{n}\)​​​​ 同阶时，我们就有可能被构造出的数据卡掉。在随机数据下，块长设为 \(\dfrac{n}{\sqrt{\dfrac{2}{3}m}}\)​ 会快一些。

我们发现，莫队算法实际上看上去仅仅是暴力的优化。但是为什么使用这种看似暴力的做法却可以通过高难度的题目呢？很显然，我们的时间复杂度在排序时被优化了。所以，排序节省了我们很多的时间。

于是又有了一种新的排序方法：奇偶性排序。

我们在选择奇数块时，按照右端点从小到大排序，在偶数块时从大到小排序，这样可以减少右端点进行大跳动的次数。

而为什么这样排序会快呢？是因为右指针移动到右边后就不需要跳回左边了，而跳回左边后处理下一个块是要跳动到右边的。很明显，这样就会优化近一半的时间复杂度。

代码：

inline bool operator < (const Query &y) const {
    return BlockId == y.BlockId ? (BlockId & 1 ? r<y.r : r>y.r) : l < y.l;
}

应用

SP3267 DQUERY - D-query

Description：求区间有多少不同的数字

Solution：我们在设计 Add 函数和 Del 函数时，其实很好设计。因为 \(a_i\) 的值域只有 \(10^6\) ，所以我们开个桶记录，每次这个数的数量都加上或减去一即可。

Code：

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 7, M = 1e6 + 7;

struct Query {
    int l, r;
    int AnsId, BlockId; // AnsId 表示时第几次询问,BlockId 表示第几块
    inline bool operator < (const Query y) const {
        return BlockId == y.BlockId ? (BlockId & 1 ? r<y.r : r>y.r) : l < y.l; // 奇偶性优化
    }
} q[M];

int a[N];
int ans[M];
int cnt[N]; // 桶

int n, m;
int block;
int l = 1, r = 0, res;

inline void Add(int x) {
    ++cnt[a[x]];

    if (cnt[a[x]] == 1)
        ++res;
}

inline void Del(int x) {
    --cnt[a[x]];

    if (!cnt[a[x]])
        --res;
}

signed main() {
    scanf("%d", &n);
    block = n / sqrt((m << 1) / 3);

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

    scanf("%d", &m);

    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].AnsId = i;
        q[i].BlockId = (q[i].l - 1) / block + 1;
    }

    sort(q + 1, q + 1 + m);

    for (int i = 1; i <= m; ++i) {
        while (l < q[i].l)
            Del(l++);

        while (l > q[i].l)
            Add(--l);

        while (r < q[i].r)
            Add(++r);

        while (r > q[i].r)
            Del(r--);

        ans[q[i].AnsId] = res; // 模板
    }

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

    return 0;
}

P2709 小B的询问

Description：求区间每个数字出现次数的平方和

Solution：因为 \(a_i\) 的值域只有 \(5 \times10^4\) ，所以我们开个桶记录每个数出现次数。那么平方和怎么计算呢？

注意到

\[(a+1)^2=a^2+2a+1 \]

于是我们就可以很轻松地设计 Add 函数和 Del 函数了。

Code：

#include <cmath>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
const int N = 5e4 + 7;

struct Query {
    int l, r;
    int AnsId, BlockId;
    inline bool operator < (const Query y) const {
        return BlockId == y.BlockId ? (BlockId & 1 ? r<y.r : r>y.r) : l < y.l;
    }
} q[N];

ll a[N];
ll cnt[N];
ll ans[N];

int n, m, k;
int block, l = 1, r;
ll res;

inline void Add(int x) {
    res += (cnt[a[x]] << 1) + 1;
    ++cnt[a[x]];
}

inline void Del(int x) {
    res -= (cnt[a[x]] << 1) - 1;
    --cnt[a[x]];
}

signed main() {
    scanf("%d%d%d", &n, &m, &k);
    block = n / sqrt((m << 1) / 3);

    for (int i = 1; i <= n; ++i)
        scanf("%lld", a + i);

    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].AnsId = i;
        q[i].BlockId = (q[i].l - 1) / block + 1;
    }

    sort(q + 1, q + 1 + m);

    for (int i = 1; i <= m; ++i) {
        while (l < q[i].l)
            Del(l++);

        while (l > q[i].l)
            Add(--l);

        while (r < q[i].r)
            Add(++r);

        while (r > q[i].r)
            Del(r--);

        ans[q[i].AnsId] = res;
    }

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

    return 0;
}

P1494 [国家集训队] 小 Z 的袜子

Description：查询区间内选到两数相同的概率

Solution：将题意用式子可以表示为

\[\dfrac{\sum \dfrac{a_k(a_k-1)}{2}}{\dfrac{len(len-1)}{2}} \]

（其中 \(a_k\) 表示每个数字出现的次数，\(len\) 表示区间长度

将式子化简，可得

\[\dfrac{\sum a_k^2 - \sum a_k}{len(len-1)} \]

由 \(a_k\) 的定义可得 \(\sum a_k=len\)

所以原式等价于

\[\dfrac{\sum a_k^2 - len}{len(len-1)} \]

那么问题就转化为求区间数字出现次数平方和，按上题思路解决即可

Code：

#include <map>
#include <set>
#include <cmath>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
const int N = 5e4 + 7;

struct Query {
    int l, r;
    int AnsId, BlockId;
    inline bool operator < (const Query y) const {
        return BlockId == y.BlockId ? (BlockId & 1 ? r<y.r : r>y.r) : l < y.l;
    }
} q[N];

ll a[N];
ll cnt[N];
pair<ll, ll> ans[N];

int n, m;
int block, l = 1, r;
ll res;

inline void Add(int x) {
    res += (cnt[a[x]] << 1) + 1;
    ++cnt[a[x]];
}

inline void Del(int x) {
    res -= (cnt[a[x]] << 1) - 1;
    --cnt[a[x]];
}

template<class T>
inline T gcd(T gcd_a, T gcd_b) {
    while (gcd_b ^= gcd_a ^= gcd_b ^= gcd_a %= gcd_b);

    return gcd_a;
}

signed main() {
    scanf("%d%d", &n, &m);
    block = n / sqrt((m << 1) / 3);

    for (int i = 1; i <= n; ++i)
        scanf("%lld", a + i);

    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].AnsId = i;
        q[i].BlockId = (q[i].l - 1) / block + 1;
    }

    sort(q + 1, q + 1 + m);

    for (int i = 1; i <= m; ++i) {
        while (l < q[i].l)
            Del(l++);

        while (l > q[i].l)
            Add(--l);

        while (r < q[i].r)
            Add(++r);

        while (r > q[i].r)
            Del(r--);

        if (q[i].l == q[i].r)
            ans[q[i].AnsId] = {0, 1};
        else
            ans[q[i].AnsId] = {res - (q[i].r - q[i].l + 1), (ll)(q[i].r - q[i].l + 1) *(q[i].r - q[i].l)};
    }

    for (int i = 1; i <= m; ++i)
        if (ans[i].first)
            printf("%lld/%lld\n", ans[i].first / gcd(ans[i].first, ans[i].second), ans[i].second / gcd(ans[i].first,
                    ans[i].second));
        else
            puts("0/1");

    return 0;
}

CF617E XOR and Favorite Number

我们可以先预处理出前缀异或值，由前缀和性质可知，我们的问题就变成了在前缀和数组中有多少对 \(i,j\) 满足 \(a_i \operatorname{xor} a_j = k\)，答案为 \(ans(r)-ans(l-1)\) ，为了方便我们存储左端点的时候就将其减一。

注意到

\[x \operatorname{xor} y = k \ \ \ \ \Longrightarrow \ \ \ \ x \operatorname{xor} k = y \]

所以每次加入一个数字 \(x\) 后，和 \(x\) 异或后等于 \(k\) 的数字都可以算入答案。也就是说，我们只要知道区间内有多少个数字 \(y\) 满足 $y=x \operatorname{xor} k $​，就可以知道答案要加上几。删除时同理。

代码：

#include <cmath>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
const int N = 1e5 + 7, MAX = 2e6 + 7;

struct Query {
    int l, r;
    int AnsId, BlockId;
    inline bool operator < (const Query y) const {
        return BlockId == y.BlockId ? (BlockId & 1 ? r<y.r : r>y.r) : l < y.l;
    }
} q[N];

ll a[N];
ll cnt[MAX];
ll ans[N];

int n, m, k;
int block, l = 1, r;
ll res;

inline void Add(int x) {
    res += cnt[a[x] ^ k];
    ++cnt[a[x]];
}

inline void Del(int x) {
    --cnt[a[x]];
    res -= cnt[a[x] ^ k];
}

signed main() {
    scanf("%d%d%d", &n, &m, &k);
    block = sqrt(n);

    for (int i = 1; i <= n; ++i) {
        scanf("%lld", a + i);
        a[i] ^= a[i - 1]; // 直接赋值为前缀异或数组
    }

    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &q[i].l, &q[i].r);
        --q[i].l;
        q[i].AnsId = i;
        q[i].BlockId = (q[i].l - 1) / block + 1;
    }

    sort(q + 1, q + 1 + m);

    for (int i = 1; i <= m; ++i) {
        while (l < q[i].l)
            Del(l++);

        while (l > q[i].l)
            Add(--l);

        while (r < q[i].r)
            Add(++r);

        while (r > q[i].r)
            Del(r--);

        ans[q[i].AnsId] = res;
    }

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

    return 0;
}

CF220B Little Elephant and Array

普通莫队操作，Add 和 Del 时判断出现次数是否和其相等即可。

但是值域大到 \(10^9\) ，无法直接用桶存储。

注意到 \(>n\) 的数字都不可能对答案产生贡献，所以我们去掉这些数，这样值域就是 \(10^5\) 的了。

代码：

#include <cmath>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
const int N = 1e5 + 7;

struct Query {
    int l, r;
    int AnsId, BlockId;
    inline bool operator < (const Query y) const {
        return BlockId == y.BlockId ? (BlockId & 1 ? r<y.r : r>y.r) : l < y.l;
    }
} q[N];

int a[N];
int cnt[N];
int ans[N];

int n, m, k;
int block, l = 1, r;
ll res;

inline void Add(int x) {
    if (~a[x]) {
        if (cnt[a[x]] == a[x])
            --res;

        ++cnt[a[x]];

        if (cnt[a[x]] == a[x])
            ++res;
    }
}

inline void Del(int x) {
    if (~a[x]) {
        if (cnt[a[x]] == a[x])
            --res;

        --cnt[a[x]];

        if (cnt[a[x]] == a[x])
            ++res;
    }
}

signed main() {
    scanf("%d%d", &n, &m);
    block = sqrt(n);

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

        if (a[i] > n)
            a[i] = -1;
    }

    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].AnsId = i;
        q[i].BlockId = (q[i].l - 1) / block + 1;
    }

    sort(q + 1, q + 1 + m);

    for (int i = 1; i <= m; ++i) {
        while (l < q[i].l)
            Del(l++);

        while (l > q[i].l)
            Add(--l);

        while (r < q[i].r)
            Add(++r);

        while (r > q[i].r)
            Del(r--);

        ans[q[i].AnsId] = res;
    }

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

    return 0;
}

标签：cnt,int,res,BlockId,Add,--,算法,莫队
From： https://www.cnblogs.com/wshcl/p/MoDui.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99