Processing math: 100%

「Luogu P4168」「Violet」蒲公英

发表于 | 更新于 | 分类于 | 阅读次数：46

Description

给定 n 个数 ai，m 个询问，求区间 [l,r] 中的最小众数，强制在线。

(1≤n≤4×104,1≤m≤5×104,1≤ai≤109)

Source

[Luogu]P4168

Solution 1

考虑 分块 。我们可以预处理出 fi,j 为第 i 个块到第 j 个块的区间最小众数，那样区间 [l,r] 的答案只有可能是 中间所有块的区间最小众数，左边多余块中的数 或 右边多余块中的数（如图）。

E2wxnx.png

很容易在 O(块的大小×n) 的时间内预处理出所有的 fi,j，但是怎么求出左右多余块中的数在区间 [l,r] 中的出现次数呢？我们可以用 vector 存下每一个 ai 在序列中的所有出现位置（要先离散化）。在询问时，对于左右多余块中的每一个数 x，我们可以二分找到端点 l,r 在 x 对应的 vector 中的位置（可以用 STL 中的 lower_bound 和 upper_bound），相减即是 x 在区间 [l,r] 中的出现次数。注意如果该数的出现次数与当前答案的出现次数相同，但这个数更小，也要更新答案，因为要求的是最小众数。

设块的大小为 S，则总时间复杂度为 预处理 O(n2S) + 查询 O(mSlogn)，根据 均值不等式，可知取 S=n√mlogn 时总时间复杂度最小，为 O(n√mlogn) 。

Code 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
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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 4e4, MAX_SIZE = 1e3;
int n, m, blockSize, blockNum, lastans, a[MAXN + 5], b[MAXN + 5], cnt[MAXN + 5], bel[MAXN + 5];
int blockL[MAX_SIZE + 5], blockR[MAX_SIZE + 5], f[MAX_SIZE + 5][MAX_SIZE + 5], num[MAX_SIZE + 5][MAX_SIZE + 5];
vector<int> site[MAXN + 5];

inline void init() {
    blockSize = n / sqrt(m * log2(n));
    blockNum = n / blockSize + (n % blockSize > 0);
    sort(b + 1, b + n + 1);
    int len = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;//离散化
        site[a[i]].push_back(i);//存下每一个 a[i] 出现的位置
        bel[i] = (i - 1) / blockSize + 1;
    }
    for (int i = 1; i <= blockNum; ++i)
        blockL[i] = (i - 1) * blockSize + 1, blockR[i] = i * blockSize;
    blockR[blockNum] = n;
    for (int i = 1; i <= blockNum; ++i) {
        memset(cnt, 0, sizeof (cnt));
        int maxn = 0, mode = 0;//maxn 记录众数出现次数，mode 记录最小众数
        for (int j = i; j <= blockNum; ++j) {
            for (int k = blockL[j]; k <= blockR[j]; ++k) {
                ++cnt[a[k]];
                if (cnt[a[k]] > maxn || (cnt[a[k]] == maxn && a[k] < mode)) {
                    //如果出现次数比 maxn 大 或 出现次数与 maxn 相同但这个数比当前记录的 mode 小
                    maxn = cnt[a[k]];
                    mode = a[k];//更新最优值
                }
            }
            num[i][j] = maxn;//记录第 i 个块到第 j 个块众数的出现次数 
            f[i][j] = mode;//记录第 i 个块到第 j 个块的最小众数 
        }
    }
}

inline int query(int l, int r) {
    int posL, posR, mode = 0, maxn = 0;
    if (bel[l] == bel[r]) {//l,r 在同一个块
        for (int i = l; i <= r; ++i) {
            posL = lower_bound(site[a[i]].begin(), site[a[i]].end(), l) - site[a[i]].begin();
            posR = upper_bound(site[a[i]].begin(), site[a[i]].end(), r) - site[a[i]].begin();//二分找到 l,r 的位置
            if (posR - posL > maxn || (posR - posL == maxn && a[i] < mode)) {
                //判断能否更新答案
                maxn = posR - posL;
                mode = a[i];
            }
        }
        return b[mode];//mode 是离散化后的值，b[mode] 才是原序列中的值
    }
    maxn = num[bel[l] + 1][bel[r] - 1];//中间完整块众数的出现次数
    mode = f[bel[l] + 1][bel[r] - 1];//中间完整块的最小众数
    for (int i = l; i <= blockR[bel[l]]; ++i) {
        posL = lower_bound(site[a[i]].begin(), site[a[i]].end(), l) - site[a[i]].begin();
        posR = upper_bound(site[a[i]].begin(), site[a[i]].end(), r) - site[a[i]].begin();
        if (posR - posL > maxn || (posR - posL == maxn && a[i] < mode)) {
            maxn = posR - posL;
            mode = a[i];
        }
    }//处理左边多余块的每一个数
    for (int i = blockL[bel[r]]; i <= r; ++i) {
        posL = lower_bound(site[a[i]].begin(), site[a[i]].end(), l) - site[a[i]].begin();
        posR = upper_bound(site[a[i]].begin(), site[a[i]].end(), r) - site[a[i]].begin();
        if (posR - posL > maxn || (posR - posL == maxn && a[i] < mode)) {
            maxn = posR - posL;
            mode = a[i];
        }
    }//处理右边多余块的每一个数
    return b[mode];
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        b[i] = a[i];
    }
    init();
    for (int l, r, i = 1; i <= m; ++i) {
        read(l), read(r);
        l = (l + lastans - 1) % n + 1, r = (r + lastans - 1) % n + 1;//强制在线
        if (l > r) swap(l, r); 
        write(lastans = query(l, r));
        putchar('\n');
    }
    return 0;
}

Solution 2

考虑怎么优化上述做法（即减少查询的时间复杂度）。

很容易发现查询时答案在区间 [l,r] 中的出现次数其实是单调不减的。

我们可以预处理出 posi，表示 i 的位置在 ai 的 vector 中对应第几个数。假设当前我们已经知道当前的最小众数是 mode，且 mode 的出现次数为 maxn 。左边和右边多余的块分类讨论：

对于左边多余块中的某个数 x，x 在其对应 vector 中的位置是 posx 。我们只需要判断 x 出现的次数是否大于或等于 maxn 即可，因为如果这个数出现的次数小于 maxn，就不可能更新答案。如果 x 第 posx+maxn 次出现的位置 ≤r，就说明区间 [l,r] 中 x 的出现次数为 maxn+1，比当前答案更优。如果 x 第 posx+maxn−1 次出现的位置 ≤r，且 x 比答案小，就说明 x 也能更新答案。

E22tbj.png

右边多余的块同理，只是变成了判断 x 第 posx−maxn 次出现的位置是否 ≥l 。

E22YrQ.png

写代码时有很多细节需要注意。比如要先判断 vector 的下标是否小于 0 或者超过 size，然后再访问。

很显然这种做法在查询时不需要二分，时间复杂度少一只 log 。设块的大小为 S，则总时间复杂度为 预处理 O(n2S) + 查询 O(mS)，根据 均值不等式，可知取 S=n√m 时总时间复杂度最小，为 O(n√m) 。

Code 2

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 4e4, MAX_SIZE = 500;
int n, m, blockSize, blockNum, lastans, a[MAXN + 5], b[MAXN + 5], cnt[MAXN + 5], bel[MAXN + 5], pos[MAXN + 5];
int blockL[MAX_SIZE + 5], blockR[MAX_SIZE + 5], f[MAX_SIZE + 5][MAX_SIZE + 5], num[MAX_SIZE + 5][MAX_SIZE + 5];
vector<int> site[MAXN + 5];

inline void init() {
    blockSize = n / sqrt(m);
    blockNum = n / blockSize + (n % blockSize > 0);
    sort(b + 1, b + n + 1);
    int len = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) {
        a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;//离散化
        pos[i] = site[a[i]].size();//pos[i] 表示 i 的位置在 a[i] 的 vector 中对应第几个数
        site[a[i]].push_back(i);//存下每一个 a[i] 出现的位置
        bel[i] = (i - 1) / blockSize + 1;
    }
    for (int i = 1; i <= blockNum; ++i)
        blockL[i] = (i - 1) * blockSize + 1, blockR[i] = i * blockSize;
    blockR[blockNum] = n;
    for (int i = 1; i <= blockNum; ++i) {
        memset(cnt, 0, sizeof (cnt));
        int maxn = 0, mode = 0;
        for (int j = i; j <= blockNum; ++j) {
            for (int k = blockL[j]; k <= blockR[j]; ++k) {
                ++cnt[a[k]];
                if (cnt[a[k]] > maxn || (cnt[a[k]] == maxn && a[k] < mode)) {
                    maxn = cnt[a[k]];
                    mode = a[k];
                }
            }
            num[i][j] = maxn;//记录第 i 个块到第 j 个块众数的出现次数 
            f[i][j] = mode;//记录第 i 个块到第 j 个块的最小众数 
        }
    }//预处理方法与之前相同
}

inline int query(int l, int r) {
    int mode = 0, maxn = 0;
    if (bel[l] == bel[r]) {//l,r 在同个一块
        for (int i = l; i <= r; ++i) {
            if (pos[i] + maxn - 1 >= 0 && pos[i] + maxn - 1 < (int) site[a[i]].size() &&
            site[a[i]][pos[i] + maxn - 1] >= l && site[a[i]][pos[i] + maxn - 1] <= r && a[i] < mode)
                mode = a[i];//判断出现次数相同但 a[i] 更小的情况，注意边界
            for (; pos[i] + maxn < (int) site[a[i]].size() && site[a[i]][pos[i] + maxn] <= r; ++maxn)
                mode = a[i];//判断 a[i] 出现次数比答案更多的情况，maxn 单调不减
        }
        return b[mode];//mode 是离散化后的值，b[mode] 才是原序列中的值
    }
    maxn = num[bel[l] + 1][bel[r] - 1];//中间完整块众数的出现次数
    mode = f[bel[l] + 1][bel[r] - 1];//中间完整块的最小众数
    for (int i = l; i <= blockR[bel[l]]; ++i) {
        if (pos[i] + maxn - 1 >= 0 && pos[i] + maxn - 1 < (int) site[a[i]].size() &&
        site[a[i]][pos[i] + maxn - 1] >= l && site[a[i]][pos[i] + maxn - 1] <= r && a[i] < mode)
            mode = a[i];
        for (; pos[i] + maxn < (int) site[a[i]].size() && site[a[i]][pos[i] + maxn] <= r; ++maxn)//判断第 pos[i] + maxn 个 a[i] 是否在询问范围内
            mode = a[i];
    }//处理左边多余块的每一个数
    for (int i = blockL[bel[r]]; i <= r; ++i) {
        if (pos[i] - maxn + 1 >= 0 && pos[i] - maxn + 1 < (int) site[a[i]].size() &&
        site[a[i]][pos[i] - maxn + 1] >= l && site[a[i]][pos[i] - maxn + 1] <= r && a[i] < mode)
            mode = a[i];
        for (; pos[i] - maxn >= 0 && site[a[i]][pos[i] - maxn] >= l; ++maxn)//判断第 pos[i] - maxn 个 a[i] 是否在询问范围内
            mode = a[i];
    }//处理右边多余块的每一个数
    return b[mode];
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        b[i] = a[i];
    }
    init();
    for (int l, r, i = 1; i <= m; ++i) {
        read(l), read(r);
        l = (l + lastans - 1) % n + 1, r = (r + lastans - 1) % n + 1;//强制在线
        if (l > r) swap(l, r); 
        write(lastans = query(l, r));
        putchar('\n');
    }
    return 0;
}

本文标题:「Luogu P4168」「Violet」蒲公英

文章作者:Heartlessly

发布时间:2019年05月08日 - 21:17:54

最后更新:2019年05月10日 - 18:33:30

原始链接:https://heartlessly.github.io/problems/luogu-p4168/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0 comments
Anonymous
Markdown is supported

Be the first person to leave a comment!

0%