Zth's Blog

记录学习路上的点滴

0%

牛客挑战赛61 B “经典问题” + 区间mex

发表于 更新于 分类于

补题 + 区间$mex$模板

题目

题目描述

给定一个序列，$m$次查询区间的$mex$值，$mex$表示最小的没出现过的自然数，$n,m ≤ 10^5$。显然可以使用经典算法轻易解决这个经典问题。

现在蒟蒻 djy 魔改了一下它，给定一个$0$到$n - 1$的排列，$m$次查询区间的$mex$值，但是$n, m$变大了，你能帮帮他吗?

$n,m ≤ 10^7$，输入数据在程序内生成。

输入描述

第一行给出$n, m$

以下为数据生成模板

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
int a[10000001],c[10000002][2],n,m;
unsigned int rd;
inline int rnd(int mod,int seed)
{
    rd^=(1<<13);
    rd^=(rd>>7);
    rd^=(rd<<20);
    rd^=(rd>>3);
    rd^=(rd<<10);
    rd^=(rd<<5);
    rd^=(1<<2);
    return rd%mod+seed;
}
// 生成序列 a
void make_sequence()
{
    for(int i=1;i<=n;i++)
    {
        a[i]=i-1;
    }
    for(int i=1;i<=n;i++)
    {
        swap(a[i],a[rnd(n,1)]);
    }
}
// 生成一个询问，表示查询区间 [l,r] 的 mex 
pair<int,int> make_query()
{
    int l=rnd(n,1);
    int r=rnd(n+1-l,l);
    return make_pair(l,r);
}

输出描述

一行一个整数， 表示所有答案的异或和

样例

输入

5 6

输出

6

题解

思路

一看到数据随机， 以为是什么规律题， 或者考察了区间$mex$的某种性质， 或者关于随机的某种技巧

但是没想到其实是个正经题， 和数据随不随机没有关系

注意题目中给出的是$0$到$n - 1$的排列， 这是解决本题的关键。 区间$mex$定义为区间内没有出现过的最小自然数， 那么对于一个询问$[l, r]$， 我们要找的就是$a[1, l - 1], a[r + 1, n]$中最小的数， 因为这是一个排列， $0$到$n - 1$中所有的数都在$a$中出现了一次， 所以这个算法是正确的

代码

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
#include <iostream>
#include <cstdio>
#include <map>

int pn[10000007], ln[10000007];
int ans;

int a[10000001],c[10000002][2],n,m;
unsigned int rd;
inline int rnd(int mod,int seed)
{
    rd^=(1<<13);
    rd^=(rd>>7);
    rd^=(rd<<20);
    rd^=(rd>>3);
    rd^=(rd<<10);
    rd^=(rd<<5);
    rd^=(1<<2);
    return rd%mod+seed;
}
// 生成序列 a
void make_sequence()
{
    for(int i=1;i<=n;i++)
    {
        a[i]=i-1;
    }
    for(int i=1;i<=n;i++)
    {
        std:: swap(a[i],a[rnd(n,1)]);
    }
}
// 生成一个询问，表示查询区间 [l,r] 的 mex
std:: pair<int,int> make_query()
{
    int l=rnd(n,1);
    int r=rnd(n+1-l,l);
    return std:: make_pair(l,r);
}

int main()
{
    scanf("%d%d", &n, &m);

    make_sequence();

    pn[0] = n;
    for(int i = 1; i <= n; i ++) pn[i] = std:: min(pn[i - 1], a[i]);

    ln[n + 1] = n;
    for(int i = n; i >= 1; i --) ln[i] = std:: min(ln[i + 1], a[i]);

    for(int i = 1; i <= m; i ++)
    {
        std:: pair<int, int> tmp = make_query();

        ans ^= std:: min(pn[tmp.first - 1], ln[tmp.second + 1]);
    }
    
    printf("%d\n", ans);

    return 0;
}

区间$mex$

如上题所描述的， 是一个经典问题， 这里采用的例题为洛谷P4137 Rmq Problem / mex

通常来说求解区间$mex$有两种方法： 离线和在线做法。 离线又可以用莫队 + 权值分块或者线段树， 在线好像只能用权值主席树

莫队 + 权值分块

思路

经典的莫队操作， 将所有询问$[l, r]$按$\frac{l}{\sqrt n}$为第一关键字， $r$为第二关键字从小到大排序然后依次对每个询问移动$l, r$， 过程中维护两个数组：

$cnt[x]: $ $[l, r]$中$x$出现的次数

$bs[y] : $ $[l, r]$中属于第$y$个权值块的$x$的个数。 假设$max_{a_i} = mx$， 我们按照权值分块后， $bs[0]$维护的就是$[l, r]$中属于$[0, \sqrt {mx} - 1]$的$x$个数， $bs[1]$维护的就是$[l, r]$中属于$[\sqrt {mx}, 2 \times \sqrt {mx} - 1]$的$x$个数， 以此类推3

这样对于一个询问， 我们移动完$[l, r]$并维护好两个数组后， 我们只需要用$O(\sqrt {mx})$的时间遍历一下所有的$bs[]$， 找到第一个$bs[y] \neq \sqrt {mx}$的块号$y$， 然后花$O(\sqrt {mx})$的时间找到这个块内第一个没有出现也就是$cnt[x] = 0$的$x$， 这次询问的答案就是$x$，一次询问查找答案的时间复杂度是$O(2 \times \sqrt {mx}) = O(\sqrt {mx})$， 总查找答案的时间复杂度为$O(m \times \sqrt {mx})$

算法的总时间复杂度要在加上莫队时间复杂度， $2 \times 10^5$肯定是没有问题的

代码

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

int n, m;
int a[210005];
int sqn; // 根号n
struct Q
{
    int l, r, num;

    bool operator < (Q tmp) const
    {
        int b1 = l / sqn, b2 = tmp.l / sqn;

        if(b1 < b2)
            return true;
        else if(b1 > b2)
            return false;
        else
            return r < tmp.r;
    }
} q[210005];
int bs[210005], cnt[210005];
int ans[210005];

void Modui()
{
    std:: sort(q + 1, q + m + 1);

    int l = 0, r = 0;
    cnt[0] = bs[0] = 1;

    for(int i = 1; i <= m; i ++) // 莫队经典操作
    {
        int ql = q[i].l, qr = q[i].r, num = q[i].num;

        if(l < ql)
            for(int j = l; j < ql; j ++)
                cnt[a[j]] --, bs[a[j] / sqn] -= (cnt[a[j]] == 0);
        else if(l > ql)
            for(int j = l - 1; j >= ql; j --)
                bs[a[j] / sqn] += (cnt[a[j]] == 0), cnt[a[j]] ++;

        if(r < qr)
            for(int j = r + 1; j <= qr; j ++)
                bs[a[j] / sqn] += (cnt[a[j]] == 0), cnt[a[j]] ++;
        else if(r > qr)
            for(int j = r; j > qr; j --)
                cnt[a[j]] --, bs[a[j] / sqn] -= (cnt[a[j]] == 0);

        l = ql;
        r = qr;

        for(int j = 0; ; j ++) // 查找mex
            if(bs[j] != sqn)
            {
                for(int k = j * sqn; ; k ++)
                    if(! cnt[k])
                    {
                        ans[num] = k;

                        break;
                    }

                break;
            }
    }
}

int main()
{
    scanf("%d%d", &n, &m); sqn = sqrt(n);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    for(int i = 1; i <= m; i ++)
        scanf("%d%d", &q[i].l, &q[i].r), q[i].num = i;

    Modui();

    for(int i = 1; i <= m; i ++) printf("%d\n", ans[i]);

    return 0;
}

对于本题， 数据中可能会出现$n$小， $max_{a_i}$比较大的情况， 这样的话$sqn$大小应该不能代表权值分块的块大小

但是我们注意到， $a_i > n$的情况下$a_i$是无意义的， 因为对于$n$个数的序列而言， 其$mex$最大值也就能到$n$， 不可能比$n$要大， 所以权值分块的块大小是根据$n$的大小定的， 但是$bs[]$的大小一定要开的和$max_{a_i}$一样

当然也可以将$bs[]$开的和$n$一样， 这个时候只需要把所有的$a_i > n$的$a_i$都变成$n + 1$就可以了， 所以实则查找答案的时间复杂度为$O(m \sqrt n)$

莫队

莫队是一种优秀的处理区间询问的离线算法， 这里主要讨论一下算法的时间复杂度

众所周知， 莫队的时间复杂度来源于$l, r$的移动次数

$r: $在询问的每一个块中， 由于$r$是严格递增的， 所以对于每个块$r$最多移动$n$次， 由于一共有$\sqrt n$个块， 所以这一部分的时间复杂度为$O(n \sqrt n)$； 对于不在同一个块的询问， 即从第$i - 1$个询问到第$i$个询问时左端点所属的块变化了， 这时右端点也最多移动$n$次， 但是这种变化最多只有$ \sqrt n - 1$次(因为只有$\sqrt n$个询问块)， 所以这一部分的时间复杂度也是$O(n \sqrt n)$

所以$r$的时间复杂度为$O(2 \times n \sqrt n)$， 也就是$O(n \sqrt n)$

$l: $ 对于不在同一个块的询问， $l$最多移动$2 \sqrt n$次， 这种变化最多只有$\sqrt n - 1$次， 所以这部分时间复杂度为$O(n)$； 在同一个块的内的询问最多有$m$个， 而在每个块内$l$每两个询问之间最多移动$\sqrt n$次(因为块大小只有$\sqrt n$)， 所以这部分时间复杂度为$O(m \sqrt n)$

所以$l$的时间复杂度为$O(m \sqrt n + n) = O(m \sqrt n)$

所以算法的总时间复杂度为$O((m + n) \sqrt n)$

权值主席树

思路

第$i$棵主席树的叶子节点表示的是$a_1, a_2, …, a_i$中的所有权值最后一次出现的位置， 每个节点维护区间最小值

当我们要查询$[l, r]$的$mex$时， 我们在第$r$棵主席树上查询， 二分找到最后出现位置$ < l$的最小权值， 这个权值就是答案

代码

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 <iostream>
#include <cstdio>
#include <vector>

int n, m;
struct Node
{
    int ls, rs;
    int val, dat;
};

struct St
{
    std:: vector<Node> vct;
    int tot, root[210005];

    void Init()
    {
        tot = 0;
        for(int i = 0; i <= 200000; i ++) root[i] = 0;

        vct.clear();
        vct.push_back((Node){0, 0, 0, 0});
    }

    int Addnode()
    {
        tot ++;

        vct.push_back((Node){0, 0, 0, 0});

        return tot;
    }

    int Modify(int l, int r, int rt, int p, int v)
    {
        int now = Addnode();

        vct[now] = vct[rt];

        if(l == r)
        {
            vct[now].dat = vct[now].val = v;

            return now;
        }

        int mid = (l + r) >> 1;

        if(p <= mid)
            vct[now].ls = Modify(l, mid, vct[rt].ls, p, v);
        else
            vct[now].rs = Modify(mid + 1, r, vct[rt].rs, p, v);

        vct[now].dat = std:: min(vct[vct[now].ls].dat, vct[vct[now].rs].dat);

        return now;
    }

    int Query(int l, int r, int rt, int ql) // 二分找答案
    {
        if(!rt || l == r) return l;

        int mid = (l + r) >> 1;

        if(vct[vct[rt].ls].dat < ql)
            return Query(l, mid, vct[rt].ls, ql);
        else
            return Query(mid + 1, r, vct[rt].rs, ql);
    }
};

int main()
{
    St st;
    st.Init();

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
    {
        int a;
        scanf("%d", &a);

        st.root[i] = st.Modify(0, 200001, st.root[i - 1], a, i);
    }
    for(int i = 1; i <= m; i ++)
    {
        int ql, qr;
        scanf("%d%d", &ql, &qr);

        printf("%d\n", st.Query(0, 200001, st.root[qr], ql));
    }

    return 0;
}

这份代码在洛谷上只能用c++17或者20才能过， 低于这个版本会RE， 但是在我本地和Acwing就不会出问题， 不知道为什么， 我还Debug了好久

下面这个数组版的就可以在c++11的条件下通过

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
#include <iostream>
#include <cstdio>
#include <vector>

int n, m;
struct Node
{
    int ls, rs;
    int val, dat;
};

struct St
{
    Node vct[10000007];
    int tot, root[210005];

    void Init()
    {
        tot = 0;
        for(int i = 0; i <= 200001; i ++) root[i] = 0;
    }

    int Addnode()
    {
        tot ++;

        vct[tot] = (Node){0, 0, 0, 0};

        return tot;
    }

    int Modify(int l, int r, int rt, int p, int v)
    {
        int now = Addnode();

        vct[now] = vct[rt];

        if(l == r)
        {
            vct[now].dat = vct[now].val = v;

            return now;
        }

        int mid = (l + r) >> 1;

        if(p <= mid)
            vct[now].ls = Modify(l, mid, vct[rt].ls, p, v);
        else
            vct[now].rs = Modify(mid + 1, r, vct[rt].rs, p, v);

        vct[now].dat = std:: min(vct[vct[now].ls].dat, vct[vct[now].rs].dat);

        return now;
    }

    int Query(int l, int r, int rt, int ql)
    {
        if(!rt || l == r) return l;

        int mid = (l + r) >> 1;

        if(vct[vct[rt].ls].dat < ql)
            return Query(l, mid, vct[rt].ls, ql);
        else
            return Query(mid + 1, r, vct[rt].rs, ql);
    }
};

int main()
{
    St st;
    st.Init();
    
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
    {
        int a;
        scanf("%d", &a);

        st.root[i] = st.Modify(0, 200001, st.root[i - 1], a, i);
    }
    for(int i = 1; i <= m; i ++)
    {
        int ql, qr;
        scanf("%d%d", &ql, &qr);

        printf("%d\n", st.Query(0, 200001, st.root[qr], ql));
    }

    return 0;
}