banner

普通莫队模板

模板例题

Luogu P2709 小B的询问

参考代码

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
#include <cstdio>
#include <algorithm>

const int N = 5e4, M = 5e4, K = 5e4, BLOCK = 223;

struct query {
    int i, l, r;
    bool operator<(query x) {
        return (l - 1)/BLOCK != (x.l - 1)/BLOCK ? (l - 1)/BLOCK < (x.l - 1)/BLOCK : r < x.r;
    }
} q[M + 1];

int a[N + 1], cnt[K + 1];
long long ans_tmp, ans[M + 1];

void move(int i, int sign) {
    ans_tmp -= cnt[a[i]] * cnt[a[i]];
    cnt[a[i]] += sign;
    ans_tmp += cnt[a[i]] * cnt[a[i]];
}

int main() {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++) {
        q[i].i = i;
        scanf("%d%d", &q[i].l, &q[i].r);
    }        
    std::sort(q + 1, q + m + 1);
    int l = q[1].l, r = q[1].r;
    for (int i = l; i <= r; i++) move(i, 1);
    ans[q[1].i] = ans_tmp;
    for (int i = 2; i <= m; i++) {
        while (l < q[i].l) move(l++, -1);
        while (l > q[i].l) move(--l, 1);
        while (r > q[i].r) move(r--, -1);
        while (r < q[i].r) move(++r, 1);
        ans[q[i].i] = ans_tmp;
    }
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
}

带修改莫队模板

模板例题

Luogu P1903 [国家集训队]数颜色 / 维护队列

参考代码

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
#include <cstdio>
#include <algorithm>

const int N = 133333, M = 133333, K = 1e6, BLOCK = 2609;

struct query {
    int i, l, r, t;
    bool operator<(query x) {
        return (l - 1)/BLOCK != (x.l - 1)/BLOCK ? (l - 1)/BLOCK < (x.l - 1)/BLOCK : ((r - 1)/BLOCK != (x.r - 1)/BLOCK ? (r - 1)/BLOCK < (x.r - 1)/BLOCK : i < x.i);
    }
} q[M + 1];
struct edit {
    int pos, from, to;
} e[M + 1];

int a[N + 1], b[N + 1], cnt[K + 1], ans_tmp, ans[M + 1], cnt_query;

void move(int i, int sign) {
    cnt[a[i]] += sign;
    if (sign == 1 && cnt[a[i]] == 1) ++ans_tmp;
    if (sign == -1 && cnt[a[i]] == 0) --ans_tmp;
}

void edit(int i, int sign, bool flag) {
    if (sign == 1) {
        if (flag) {
            if (cnt[e[i].to] == 0) ++ans_tmp;
            if (cnt[e[i].from] == 1) --ans_tmp;
            ++cnt[e[i].to];
            --cnt[e[i].from];
        }      
        a[e[i].pos] = e[i].to;
    } else {
        if (flag) {
            if (cnt[e[i].from] == 0) ++ans_tmp;
            if (cnt[e[i].to] == 1) --ans_tmp;
            ++cnt[e[i].from];
            --cnt[e[i].to];
        }     
        a[e[i].pos] = e[i].from;
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }        
    for (int i = 1; i <= m; i++) {
        char op;
        do {
            scanf("%c", &op);
        } while (op != 'Q' && op != 'R');        
        if (op == 'Q') {
            q[++cnt_query].t = i;
            q[cnt_query].i = cnt_query;
            scanf("%d%d", &q[cnt_query].l, &q[cnt_query].r);
        } else {
            scanf("%d%d", &e[i].pos, &e[i].to);
            e[i].from = b[e[i].pos];
            b[e[i].pos] = e[i].to;
        }
    }        
    std::sort(q + 1, q + cnt_query + 1);
    int l = q[1].l, r = q[1].r, t = 0;
    while (t < q[1].t)
        if (e[++t].pos)
            edit(t, 1, false);
    for (int i = l; i <= r; i++) move(i, 1);    
    ans[q[1].i] = ans_tmp;
    for (int i = 2; i <= cnt_query; i++) {             
        while (l < q[i].l) move(l++, -1);
        while (l > q[i].l) move(--l, 1);
        while (r > q[i].r) move(r--, -1);
        while (r < q[i].r) move(++r, 1);
        while (t < q[i].t)
            if (e[++t].pos)
                edit(t, 1, l <= e[t].pos && e[t].pos <= r);
        while (t > q[i].t) {
            if (e[t].pos)
                edit(t, -1, l <= e[t].pos && e[t].pos <= r);
            --t;
        }                            
        ans[q[i].i] = ans_tmp;
    }
    for (int i = 1; i <= cnt_query; i++)
        printf("%d\n", ans[i]);
}

回滚莫队模板（以只添加不删除为例）

模板例题

Luogu P5906 【模板】回滚莫队&不删除莫队

参考代码

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
#include <cstdio>
#include <algorithm>

const int N = 2e5, M = 2e5, BLOCK = 447;

struct query {
    int i, l, r;
    bool operator<(query x) {
        return (l - 1)/BLOCK != (x.l - 1)/BLOCK ? (l - 1)/BLOCK < (x.l - 1)/BLOCK : r < x.r;
    }
} q[M + 1];

int a[N + 1], b[N + 1], left[N + 1], right[N + 1], rightr[N + 1], ans_r, ans_all, ans[M + 1];
int left_delta[N + 1], right_delta[N + 1], rightr_delta[N + 1], left_delta_cnt, right_delta_cnt, rightr_delta_cnt;

void add(int i, int flag) {    
    if (flag == 1) {
        if (!left[a[i]]) {
            left[a[i]] = i;
            left_delta[++left_delta_cnt] = a[i];
        }
        if (!right[a[i]]) right_delta[++right_delta_cnt] = a[i];
        if (!rightr[a[i]]) rightr_delta[++rightr_delta_cnt] = a[i];
        right[a[i]] = rightr[a[i]] = i;
        ans_r = std::max(ans_r, right[a[i]] - left[a[i]]);  
    } else {
        if (!right[a[i]]) {
            right[a[i]] = i;
            right_delta[++right_delta_cnt] = a[i];
        }
        ans_all = std::max(ans_all, right[a[i]] - i);
    }    
}

void calc(int l, int r) {
    int first[N + 1];
    for (int i = l; i <= r; ++i)
        first[a[i]] = 0;
    for (int i = l; i <= r; i++) {
        if (!first[a[i]]) first[a[i]] = i;
        else ans_all = std::max(ans_all, i - first[a[i]]);
    }
}

int main() {
    int n, m;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    std::sort(b + 1, b + n + 1);
    int n_unique = std::unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; i++)
        a[i] = std::lower_bound(b + 1, b + n_unique + 1, a[i]) - b;    
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        q[i].i = i;
        scanf("%d%d", &q[i].l, &q[i].r);
    }        
    std::sort(q + 1, q + m + 1);
    int l, r;
    bool flag = true;
    for (int i = 1; i <= m; i++) {
        if ((q[i].l - 1) / BLOCK == (q[i].r - 1) / BLOCK) {
            ans_all = 0;
            calc(q[i].l, q[i].r);
            flag = true;
        } else {            
            l = ((q[i].l - 1) / BLOCK + 1) * BLOCK + 1;
            if (flag || (q[i].l - 1) / BLOCK != (q[i - 1].l - 1) / BLOCK) {
                for (int j = 1; j <= left_delta_cnt; ++j)
                    left[left_delta[j]] = 0;
                for (int j = 1; j <= rightr_delta_cnt; ++j)
                    rightr[rightr_delta[j]] = 0;
                for (int j = 1; j <= right_delta_cnt; ++j)
                    right[right_delta[j]] = 0;
                r = l - 1;
                ans_r = left_delta_cnt = rightr_delta_cnt = right_delta_cnt= 0;
            }
            flag = false;
            for (int j = 1; j <= right_delta_cnt; ++j)
                right[right_delta[j]] = 0;
            for (int j = 1; j <= rightr_delta_cnt; ++j)
                right[rightr_delta[j]] = rightr[rightr_delta[j]];
            right_delta_cnt = rightr_delta_cnt;
            while (r < q[i].r) add(++r, 1); 
            ans_all = ans_r;          
            while (l > q[i].l) add(--l, -1);
        }
        ans[q[i].i] = ans_all;
    }
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);        
}