跳转至

莫队

普通莫队

例题

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

多次查询, 每次查询从区间 \([L,R]\) 内任选两个数, 数相同的概率.

代码
C++
 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
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int belong[50005], st[50005], ed[50005];
struct MO {
    int L, R, idx;
    friend bool operator<(const MO &x, const MO &y) {
        if (belong[x.L] != belong[y.L]) {
            return x.L < y.L;
        }
        if (belong[x.L] & 1) {
            return x.R < y.R;
        }
        return x.R > y.R;
    }
};
int c[50005], cnt[50005];
i64 sum = 0;
void add(int x) {
    sum += cnt[x];
    cnt[x]++;
}
void del(int x) {
    cnt[x]--;
    sum -= cnt[x];
}
int main() {
    int n, m;
    cin >> n >> m;
    {
        int B = sqrt(n);
        int cnt = n / B;
        for (int i = 1 ; i <= B ; i++) {
            st[i] = cnt * (i - 1) + 1;
            ed[i] = cnt * i;
        }
        ed[B] = n;
        for (int i = 1 ; i <= B ; i++) {
            for (int j = st[i] ; j <= ed[i] ; j++) {
                belong[j] = i;
            }
        }
    }
    for (int i = 1 ; i <= n ; i++) {
        cin >> c[i];
    }
    vector<MO> mo;
    for (int i = 0 ; i < m ; i++) {
        int L, R;
        cin >> L >> R;
        mo.push_back({L, R, i});
    }
    sort(begin(mo), end(mo));
    vector<array<i64, 2>> ans(m);
    int L = 1, R = 0;
    for (auto &[QL, QR, idx] : mo) {
        if (QL == QR) {
            ans[idx] = {0, 1};
            continue;
        }
        while (L > QL) {
            add(c[--L]);
        }
        while (R < QR) {
            add(c[++R]);
        }
        while (L < QL) {
            del(c[L++]);
        }
        while (R > QR) {
            del(c[R--]);
        }
        i64 a = sum, b = 1LL * (R - L + 1) * (R - L) / 2;
        i64 d = __gcd(a, b);
        a /= d;
        b /= d;
        ans[idx] = {a, b};
    }
    for (int i = 0 ; i < m ; i++) {
        cout << ans[i][0] << "/" << ans[i][1] << "\n";
    }
    return 0;
}

带修莫队

例题

P1903 [国家集训队] 数颜色 / 维护队列 - 洛谷

单点修改

区间查询颜色数

代码
C++
  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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int belong[1000005], st[1000005], ed[1000005];
struct MO {
    int L, R, idx, time;
    friend bool operator<(const MO &x, const MO &y) {
        if (belong[x.L] != belong[y.L]) {
            return x.L < y.L;
        }
        if (belong[x.R] == belong[y.R]) {
            return x.time < y.time;
        }
        if (belong[x.L] & 1) {
            return x.R < y.R;
        }
        return x.R > y.R;
    }
};
int c[1000005], cnt[1000005];
vector<array<int, 2>> change(1);
vector<MO> mo;
int sum;
void add(int x) {
    if (cnt[x]++ == 0) {
        sum++;
    }
}
void del(int x) {
    if (cnt[x]-- == 1) {
        sum--;
    }
}
void modify(int now, int L, int R) {
    if (change[now][0] >= L && change[now][0] <= R) {
        del(c[change[now][0]]);
        add(change[now][1]);
    }
    swap(c[change[now][0]], change[now][1]);
}
int main() {
    int n, m;
    cin >> n >> m;
    {
        int B = pow(n, 0.3333333333);
        int cnt = n / B;
        for (int i = 1 ; i <= B ; i++) {
            st[i] = cnt * (i - 1) + 1;
            ed[i] = cnt * i;
        }
        ed[B] = n;
        for (int i = 1 ; i <= B ; i++) {
            for (int j = st[i] ; j <= ed[i] ; j++) {
                belong[j] = i;
            }
        }
    }
    for (int i = 1 ; i <= n ; i++) {
        cin >> c[i];
    }
    for (int i = 1 ; i <= m ; i++) {
        char ch;
        int a, b;
        cin >> ch >> a >> b;
        if (ch == 'Q') {
            mo.push_back({a, b, (int) mo.size(), (int) change.size() - 1});
        } else {
            change.push_back({a, b});
        }
    }
    sort(begin(mo), end(mo));
    vector<int> ans(mo.size());
    int L = 1, R = 0, now = 0;
    for (auto &[QL, QR, idx, time] : mo) {
        while (L > QL) {
            add(c[--L]);
        }
        while (R < QR) {
            add(c[++R]);
        }
        while (L < QL) {
            del(c[L++]);
        }
        while (R > QR) {
            del(c[R--]);
        }
        while (now > time) {
            modify(now--, QL, QR);
        }
        while (now < time) {
            modify(++now, QL, QR);
        }
        ans[idx] = sum;
    }
    for (int i = 0 ; i < (int) ans.size() ; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

Problem - F - Codeforces

单点修改

区间查询颜色数的 \(MEX\)

代码
C++
  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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int belong[100005];
struct MO {
    int L, R, idx, time;
    friend bool operator<(const MO &x, const MO &y) {
        if (belong[x.L] != belong[y.L]) {
            return x.L < y.L;
        }
        if (belong[x.R] == belong[y.R]) {
            return x.time < y.time;
        }
        if (belong[x.L] & 1) {
            return x.R < y.R;
        }
        return x.R > y.R;
    }
};
int a[100005], cnt[200005], mex[100005];
vector<array<int, 2>> change(1);
vector<MO> mo;
int sum;
void add(int x) {
    mex[cnt[x]]--;
    cnt[x]++;
    mex[cnt[x]]++;
}
void del(int x) {
    mex[cnt[x]]--;
    cnt[x]--;
    mex[cnt[x]]++;
}
void modify(int now, int L, int R) {
    if (change[now][0] >= L && change[now][0] <= R) {
        del(a[change[now][0]]);
        add(change[now][1]);
    }
    swap(a[change[now][0]], change[now][1]);
}
int main() {
    int n, m;
    cin >> n >> m;
    int B = pow(n, 0.6666666666);
    for (int i = 1 ; i <= n ; i++) {
        belong[i] = i / B;
    }
    vector<int> idx(1);
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        idx.push_back(a[i]);
    }
    for (int i = 1 ; i <= m ; i++) {
        int op, a, b;
        cin >> op >> a >> b;
        if (op == 1) {
            mo.push_back({a, b, (int) mo.size(), (int) change.size() - 1});
        } else {
            change.push_back({a, b});
            idx.push_back(b);
        }
    }
    sort(begin(idx), end(idx));
    idx.resize(unique(begin(idx), end(idx)) - begin(idx));
    for (int i = 1 ; i <= n ; i++) {
        a[i] = lower_bound(begin(idx), end(idx), a[i]) - begin(idx);
    }
    for (auto &[_, x] : change) {
        x = lower_bound(begin(idx), end(idx), x) - begin(idx);
    }
    sort(begin(mo), end(mo));
    vector<int> ans(mo.size());
    int L = 1, R = 0, now = 0;
    for (auto &[QL, QR, idx, time] : mo) {
        while (L > QL) {
            add(a[--L]);
        }
        while (R < QR) {
            add(a[++R]);
        }
        while (L < QL) {
            del(a[L++]);
        }
        while (R > QR) {
            del(a[R--]);
        }
        while (now > time) {
            modify(now--, QL, QR);
        }
        while (now < time) {
            modify(++now, QL, QR);
        }
        ans[idx] = 1;
        while (mex[ans[idx]]) {
            ans[idx]++;
        }
    }
    for (int i = 0 ; i < (int) ans.size() ; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

回滚莫队

不删除莫队

例题

P5906 【模板】回滚莫队&不删除莫队 - 洛谷

多次查询区间内数值相同的下标之差的绝对值的最大值

代码
C++
  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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int belong[200005], st[200005], ed[200005];
struct MO {
    int L, R, idx;
    friend bool operator<(const MO &x, const MO &y) {
        if (belong[x.L] != belong[y.L]) {
            return x.L < y.L;
        }
        return x.R < y.R;
    }
};
int a[200005];
array<int, 2> tcnt[200005], cnt[200005];
int sum = 0;
void addL(int idx) {
    if (tcnt[a[idx]][1] == 0) {
        tcnt[a[idx]][1] = idx;
    }
    tcnt[a[idx]][0] = idx;
    sum = max(sum, max(cnt[a[idx]][1], tcnt[a[idx]][1]) - tcnt[a[idx]][0]);
}
void addR(int idx) {
    if (cnt[a[idx]][0] == 0) {
        cnt[a[idx]][0] = idx;
    }
    cnt[a[idx]][1] = idx;
    sum = max(sum, cnt[a[idx]][1] - cnt[a[idx]][0]);
}
void del(int idx) {
    cnt[a[idx]] = {0, 0};
}
void rollBack(int idx) {
    tcnt[a[idx]] = {0, 0};
}
int main() {
    int n;
    cin >> n;
    {
        int B = sqrt(n);
        int cnt = n / B;
        for (int i = 1 ; i <= B ; i++) {
            st[i] = cnt * (i - 1) + 1;
            ed[i] = cnt * i;
        }
        ed[B] = n;
        for (int i = 1 ; i <= B ; i++) {
            for (int j = st[i] ; j <= ed[i] ; j++) {
                belong[j] = i;
            }
        }
    }
    vector<int> idx(1);
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        idx.push_back(a[i]);
    }
    sort(begin(idx), end(idx));
    idx.resize(unique(begin(idx), end(idx)) - begin(idx));
    for (int i = 1 ; i <= n ; i++) {
        a[i] = lower_bound(begin(idx), end(idx), a[i]) - begin(idx);
    }
    int m;
    cin >> m;
    vector<MO> mo;
    for (int i = 0 ; i < m ; i++) {
        int L, R;
        cin >> L >> R;
        mo.push_back({L, R, i});
    }
    sort(begin(mo), end(mo));
    vector<int> ans(mo.size());
    int lst = belong[mo[0].L], R = ed[lst], L = R + 1;
    for (auto &[QL, QR, idx] : mo) {
        if (belong[QL] == belong[QR]) { // 在一个块内, 暴力查询
            int temp = 0;
            for (int j = QL ; j <= QR ; j++) {
                if (tcnt[a[j]][0] == 0) {
                    tcnt[a[j]][0] = j;
                }
                tcnt[a[j]][1] = j;
                temp = max(temp, tcnt[a[j]][1] -tcnt[a[j]][0]);
            }
            for (int j = QL ; j <= QR ; j++) {
                tcnt[a[j]] = {0, 0};
            }
            ans[idx] = temp;
            continue;
        }
        if (lst != belong[QL]) {
            // 如果当前不在查询块内, 则将 L 和 R 移至块内
            while (R > ed[belong[QL]]) {
                del(R--);
            }
            while (L < ed[belong[QL]] + 1) {
                del(L++);
            }
            sum = 0;
            lst = belong[QL];
        }
        while (R < QR) { // 向右扩, 直至 R = QR
            addR(++R);
        }
        int temp = sum, L1 = L;
        while (L1 > QL) { // 新开向左扩, 直至 L1 = QL
            addL(--L1);
        }
        ans[idx] = sum;
        while (L1 < L) { // 回滚左端点
            rollBack(L1++);
        }
        sum = temp;
    }
    for (int i = 0 ; i < m ; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

C - 歴史の研究

多次查询区间 \(a_i*cnt_{a_i}\) 的最大值

代码
C++
  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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int belong[100005], st[100005], ed[100005];
struct MO {
    int L, R, idx;
    friend bool operator<(const MO &x, const MO &y) {
        if (belong[x.L] != belong[y.L]) {
            return x.L < y.L;
        }
        return x.R < y.R;
    }
};
int a[100005];
int tcnt[100005], cnt[100005];
i64 sum = 0;
vector<int> ind(1);
void add(int idx) {
    cnt[a[idx]]++;
    sum = max(sum, 1LL * cnt[a[idx]] * ind[a[idx]]);
}
void del(int idx) {
    cnt[a[idx]]--;
}
int main() {
    int n, m;
    cin >> n >> m;
    {
        int B = sqrt(n);
        int cnt = n / B;
        for (int i = 1 ; i <= B ; i++) {
            st[i] = cnt * (i - 1) + 1;
            ed[i] = cnt * i;
        }
        ed[B] = n;
        for (int i = 1 ; i <= B ; i++) {
            for (int j = st[i] ; j <= ed[i] ; j++) {
                belong[j] = i;
            }
        }
    }
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        ind.push_back(a[i]);
    }
    sort(begin(ind), end(ind));
    ind.resize(unique(begin(ind), end(ind)) - begin(ind));
    for (int i = 1 ; i <= n ; i++) {
        a[i] = lower_bound(begin(ind), end(ind), a[i]) - begin(ind);
    }
    vector<MO> mo;
    for (int i = 0 ; i < m ; i++) {
        int L, R;
        cin >> L >> R;
        mo.push_back({L, R, i});
    }
    sort(begin(mo), end(mo));
    vector<i64> ans(mo.size());
    int lst = belong[mo[0].L], R = ed[lst], L = R + 1;
    for (auto &[QL, QR, idx] : mo) {
        if (belong[QL] == belong[QR]) { // 在一个块内, 暴力查询
            i64 temp = 0;
            for (int j = QL ; j <= QR ; j++) {
                tcnt[a[j]]++;
                temp = max(temp, 1LL * tcnt[a[j]] * ind[a[j]]);
            }
            for (int j = QL ; j <= QR ; j++) {
                tcnt[a[j]]--;
            }
            ans[idx] = temp;
            continue;
        }
        if (lst != belong[QL]) {
            // 如果当前不在查询块内, 则将 L 和 R 移至块内
            while (R > ed[belong[QL]]) {
                del(R--);
            }
            while (L < ed[belong[QL]] + 1) {
                del(L++);
            }
            sum = 0;
            lst = belong[QL];
        }
        while (R < QR) { // 向右扩, 直至 R = QR
            add(++R);
        }
        i64 temp = sum;
        int L1 = L;
        while (L1 > QL) { // 新开向左扩, 直至 L1 = QL
            add(--L1);
        }
        ans[idx] = sum;
        while (L1 < L) { // 回滚左端点
            del(L1++);
        }
        sum = temp;
    }
    for (int i = 0 ; i < m ; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

不增加莫队

例题

P4137 Rmq Problem / mex - 洛谷

代码
C++
  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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int belong[200005], st[200005], ed[200005];
struct MO {
    int L, R, idx;
    friend bool operator<(const MO &x, const MO &y) {
        if (belong[x.L] != belong[y.L]) {
            return x.L < y.L;
        }
        return x.R > y.R;
    }
};
int a[200005];
int cnt[200005], tcnt[200005];
int sum = 0;
void add(int idx) {
    cnt[a[idx]]++;
}
void del(int idx) {
    if (cnt[a[idx]]-- == 1) {
        sum = min(sum, a[idx]);
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    {
        int B = sqrt(n);
        int cnt = n / B;
        for (int i = 1 ; i <= B ; i++) {
            st[i] = cnt * (i - 1) + 1;
            ed[i] = cnt * i;
        }
        ed[B] = n;
        for (int i = 1 ; i <= B ; i++) {
            for (int j = st[i] ; j <= ed[i] ; j++) {
                belong[j] = i;
            }
        }
    }
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    while (cnt[sum]) {
        sum++;
    }
    vector<MO> mo;
    for (int i = 0 ; i < m ; i++) {
        int L, R;
        cin >> L >> R;
        mo.push_back({L, R, i});
    }
    sort(begin(mo), end(mo));
    vector<int> ans(mo.size());
    int L = 1, R = n, lst = 0;
    for (auto &[QL, QR, idx] : mo) {
        // cout << QL << " " <<QR << " " << L << " " << R << "\n";
        if (belong[QL] == belong[QR]) { // 在一个块内, 暴力查询
            for (int j = QL ; j <= QR ; j++) {
                tcnt[a[j]]++;
            }
            i64 temp = 0;
            while (tcnt[temp]) {
                temp++;
            }
            for (int j = QL ; j <= QR ; j++) {
                tcnt[a[j]]--;
            }
            ans[idx] = temp;
            continue;
        }
        if (lst != belong[QL]) {
            // 如果当前不在查询块内, 则将 R 移至最后, L 移至当前块的第一个点
            while (R < n) {
                add(++R);
            }
            while (L < st[belong[QL]]) {
                del(L++);
            }
            int temp = 0;
            while (cnt[temp]) {
                temp++;
            }
            sum = temp;
            lst = belong[QL];
        }
        while (R > QR) { // R 移至 QR
            del(R--);
        }
        int temp = sum, L1 = L;
        while (L1 < QL) { // L1 移至 QL
            del(L1++);
        }
        ans[idx] = sum;
        while (L1 > L) { // L1 移回来
            add(--L1);
        }
        sum = temp;
    }
    for (int i = 0 ; i < m ; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}