Htto的小站
0%

莫队

发表于 更新于 分类于 ，

莫队

概述

莫队算法主要是用于离线解决通常不带修改只有查询的一类区间问题。如果从[l,r]的答案能够O(1)拓展到[l−1,r],[l+1,r],[l,r+1],[l,r−1]（即与[l,r]相邻的区间）的答案，那么就可以O(nn)的复杂度内求出所有询问的答案。

实现

离线后排序，顺序处理每个询问[l,r]，暴力从上一个区间转移到下一个区间答案（一步一步移动即可）。但是我们这样朴素写可能被卡掉，因为他可能类似于 (1,1),(2,10000),(3,1),(4,10000)

那怎么办呢，我们根据l分块！如果块号一样我们按r排序，否则我们就比较l，这样保证每个块的r最多移动N，同样的我们同一个块中相邻的两个询问l最多移动N。这样综合起来时间复杂度就是O(NN)啦。

下面我们看一道ABC莫队板子题

ABC242G:Range Pairing Query

给你N(1≤N≤105)个数，每个数Ai大小从[1,N]，给定很多询问，你需要计算

∑ci⌊ci/2⌋

其中ci是这个区间某个数出现的次数，注意这个maxn一定要取max(N,Q)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <algorithm>
#include <array>

using namespace std;
const int maxn = 1e6 + 5;
// 每个块sqrt N

int N;
int A[maxn];
int cnt[maxn];

namespace MD
{
    int ANS[maxn];
    int cur_ans;
    int len;
    bool cmp(array<int, 3> a1, array<int, 3> a2)
    {
        auto [l, r, id] = a1;
        auto [l2, r2, id2] = a2;

        if (l / len != l2 / len)
            return l < l2;
        return r < r2;
    }
    void inc(int x)
    {
        cur_ans -= cnt[A[x]] / 2;
        cnt[A[x]]++;
        cur_ans += cnt[A[x]] / 2;
    }
    void dec(int x)
    {
        cur_ans -= cnt[A[x]] / 2;
        cnt[A[x]]--;
        cur_ans += cnt[A[x]] / 2;
    }

    void solve(vector<array<int, 3>> &qs, int n)
    {
        len = sqrt(n);
        int L = 1, R = 0;

        sort(qs.begin(), qs.end(), cmp);
        for (int i = 0; i < qs.size(); i++)
        {
            auto [l, r, id] = qs[i];
            while (L > l) inc(--L);
            while (L < l) dec(L++);
            while (R < r) inc(++R);
            while (R > r) dec(R--);
            ANS[id] = cur_ans;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> A[i];
    int Q;
    cin >> Q;
    vector<array<int, 3>> qs;
    for (int i = 1; i <= Q; i++)
    {
        int l, r;
        cin >> l >> r;
        qs.push_back({l, r, i});
    }
    MD::solve(qs, N);
    for (int i = 1; i <= Q; i++)
        cout << MD::ANS[i] << "\n";
    return 0;
}