hyz's blog
0%

莫队算法学习笔记（一）

发表于

介绍

莫队算法主要用于可以离线处理的、不带修改的、只有查询的一类区间问题。
升级版的莫队算法可以解决带修改的区间问题。
我看过的比较好的教程：莫队算法 (Mo’s Algorithm)。

题目1: HYSBZ - 2038

题意

给一个具有n个元素的数列，然后有m个询问，查询的是某个区间任取两个数，这两个数相同的概率。

分析

莫队算法的核心是要找到[L, R]转移到[L-1, R], [L+1, R], [L, R-1], [L, R+1]时答案是怎么改变的。
具体到这道题，以[L, R]转移到[L, R+1]的情况为例，由于增加了一个元素，所以凑成两个相同的数的方案数以及总的组合数都会改变，因此我们需要维护的是各数字出现的次数以及区间大小。

代码

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
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

int n, m, a[N], b[N], l, r, len;
ll up[N], down[N];

struct node {
    int l, r, id, block;
    node() {}
    node(int l, int r, int id) {
        this->l = l;
        this->r = r;
        this->id = id;
        block = l / len;
    }
    bool operator < (const node b) const {
        if(block == b.block) return r < b.r;
        return block < b.block;
    }
}q[N];

void cal(ll &ans, int pos, int fix) {
    ans -= 1LL * b[a[pos]] * (b[a[pos]] - 1) / 2;
    b[a[pos]] += fix;
    ans += 1LL * b[a[pos]] * (b[a[pos]] - 1) / 2;
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(cin >> n >> m) {
        len = sqrt(n);
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for(int i = 0; i < m; i++) {
            scanf("%d%d", &l, &r);
            q[i] = node{l, r, i};
        }
        sort(q, q + m);
        ll ans = 0;
        l = r = 1;
        b[a[l]]++;
        for(int i = 0; i < m; i++) {
            node &t = q[i];
            while(r < t.r) cal(ans, ++r, 1);
            while(l > t.l) cal(ans, --l, 1);
            while(r > t.r) cal(ans, r--, -1);
            while(l < t.l) cal(ans, l++, -1);
            ll t0 = ans;
            ll t1 = 1LL * (t.r - t.l + 1) * (t.r - t.l) / 2;
            ll g = __gcd(t0, t1);
            t0 /= g;
            t1 /= g;
            up[t.id] = t0;
            down[t.id] = t1;
        }
        for(int i = 0; i < m; i++)
            printf("%lld/%lld\n", up[i], down[i]);
    }

    return 0;
}

题目2: SPOJ - DQUERY

题意

给一个具有n个元素的数列，然后有q个询问，查询的是某个区间不同数字的个数。

分析

我们只需要维护各数字出现的次数即可，假如在区间改变的过程，某一个数字出现的次数由1变成0，那么答案应该减1，而假如由0变成1，那么答案应该加1。

代码

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
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e6+9;
const int shift=1e3+9;
const double Eps=1e-7;

int n, m, len, a[N], b[N], l, r, sum, ans[N];

struct node {
    int l, r, id, block;
    node() {}
    node(int l, int r, int id) {
        this->l = l;
        this->r = r;
        this->id = id;
        block = l / len;
    }
    bool operator < (const node b) const {
        if(block == b.block) return r < b.r;
        return block < b.block;
    }
}q[N];

inline void cal(int &sum, int pos, int fix) {
    int &t = b[a[pos]];
    t += fix;
    if(fix == 1 && t == 1)
        sum++;
    else if(fix == -1 && t == 0)
        sum--;
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    cin >> n;
    len = sqrt(n);
    for(int i = 1; i <= n; i++)
        scanf("%d", a + i);
    cin >> m;
    for(int i = 0; i < m; i++) {
        scanf("%d%d", &l, &r);
        q[i] = node{l, r, i};
    }
    sort(q, q + m);
    l = r = sum = 1;
    b[a[1]]++;
    for(int i = 0; i < m; i++) {
        node &t = q[i];
        while(r < t.r) cal(sum, ++r, 1);
        while(l > t.l) cal(sum, --l, 1);
        while(r > t.r) cal(sum, r--, -1);
        while(l < t.l) cal(sum, l++, -1);
        ans[t.id] = sum;
    }
    for(int i = 0; i < m; i++)
        printf("%d\n", ans[i]);
    return 0;
}

题目3: Powerful array

题意

给一个具有n个元素的数列，然后有t个询问，查询的是某一区间Ks·Ks·s的和，其中s表示的是某一个数字，Ks表示的是该数字出现的次数。

分析

我们只需要维护各数字出现的次数即可。维护前，先减去该数字的贡献值，维护后，再加上该数字的贡献值。

代码

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
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e6+9;
const double Eps=1e-7;

int n, m, a[N], l, r, len, cnt[N];
ll ans, an[N];

struct node {
    int l, r, id, block;
    node() {}
    node(int l, int r, int id) {
        this->l = l;
        this->r = r;
        this->id = id;
        this->block = l / len;
    }
    bool operator < (const node t) const {
        if(t.block == block) return r < t.r;
        return block < t.block;
    }
}q[N];

void cal(ll &ans, int pos, int fix) {
    int &t = cnt[a[pos]];
    ans -= 1LL * t * t * a[pos];
    t += fix;
    ans += 1LL * t * t * a[pos];
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d", &n, &m)) {
        len = sqrt(n);
        for(int i = 1; i <= n; i++)
            scanf("%d", a + i);
        for(int i = 0; i < m; i++) {
            scanf("%d%d", &l, &r);
            q[i] = node{l, r, i};
        }
        sort(q, q + m);
        l = 1, r = 1;
        cnt[a[1]]++;
        ans = a[1];
        for(int i = 0; i < m; i++) {
            node t = q[i];
            while(r < t.r) cal(ans, ++r, 1);
            while(l > t.l) cal(ans, --l, 1);
            while(r > t.r) cal(ans, r--, -1);
            while(l < t.l) cal(ans, l++, -1);
            an[t.id] = ans;
        }
        for(int i = 0; i < m; i++)
            printf("%I64d\n", an[i]);
    }

    return 0;
}