(luogu4137)Rmq Problem / mex

发表于 分类于 ，

原题链接

思路:

本题有两种做法，一种是基于线段树的做法，还有一种是基于莫队的做法.

线段树:

与 HH 的项链类似， 将区间按 r 排序。然后从左到右扫描原数组.

然后维护一颗权值线段树 , 维护当前某个值出现的最右端位置 , 区间维护其最小值.

对于每个询问，在线段树中查找最右端位置小于 l 的最小值 , 即为答案.

由于线段树每次只改变一个位置，所以也可以写成主席树 , 这样就可以在线解决.

时间复杂度为 \(O(mlog(max\{a\}))\).

莫队:

显然直接统计个数然后暴力查找是过不去的，使用线段树的时间复杂度为 \(O(nlog(a)\sqrt n)\) 也可能会挂.

这时需要用到值域分块.

具体来讲，先将值域分为若干个分块， 统计值的个数时同时更新该值所在分块中存在的值的个数。查询时先查询分块， 再在分块内暴力查找最小未出现值.

这样的时间复杂度为 \(O(n \sqrt n + m \sqrt 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
64
65
66
67
68
69
70
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int Mn(200500);
template<typename T> void qrd(T& x) {   //快读
    x = 0;
    int c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c - '0';
        c = getchar();
    }
}
template<typename T, typename... Ts> void qrd(T& x, Ts&... xs) {
    qrd(x); qrd(xs...);
}
struct Tnd {
    int v;
    int ls, rs;
}t[Mn*20];  //主席树
int rts[Mn];
int newTnd(const Tnd& x) {  //开点
    static int tc(0);
    t[++tc] = x;
    return tc;
}
void mdf(int& p,int l,int r,int mp,int mx) {    //主席树修改
    p = newTnd(t[p]);
    if(l==r) {
        t[p].v = mx;
        return;
    }
    int mid((l+r)/2);
    if(mp<=mid) {
        mdf(t[p].ls,l,mid,mp,mx);
    } else {
        mdf(t[p].rs,mid+1,r,mp,mx);
    }
    t[p].v = min(t[t[p].ls].v,t[t[p].rs].v);    //区间取最小
}
int qry(int p,int l,int r,int ql) { //查询
    if(l==r) {
        return l;
    }
    int mid((l+r)/2);
    if(t[t[p].ls].v<ql) {
        return qry(t[p].ls,l,mid,ql);
    } else {
        return qry(t[p].rs,mid+1,r,ql);
    }
}

int main() {
    int n,m;
    qrd(n,m);
    for(int i(1);i<=n;++i) {
        int a; qrd(a);
        rts[i] = rts[i-1];
        mdf(rts[i],0,Mn,a,i);   //修改值最右侧位置
    }
    while(m--) {    //在线查询
        int l,r;
        qrd(l,r);
        printf("%d\n",qry(rts[r],0,Mn,l));
    }
    return 0;
}

莫队: 

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
//值域的分块长度为500
#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
const int Mn(200500), Mm(200500), Ma(250500), Ml(500);

template<typename T> void qrd(T& x) {
    x = 0;
    int c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c - '0';
        c = getchar();
    }
}
template<typename T, typename... Ts> void qrd(T& x, Ts&... xs) {
    qrd(x); qrd(xs...);
}

int nbl(0); //n分块长度
inline int getB(int x,int bl) { //获取分块编号
    return x/bl + 1;
}
int a[Mn];
struct Qd {
    int l, r, i;
    bool operator < (const Qd& rhs) const { //排序
        if(getB(l,nbl)==getB(rhs.l,nbl)) {
            return (getB(l,nbl)&1) ? r<rhs.r : r>rhs.r;
        }
        return l<rhs.l;
    }
} aq[Mm];

int cnt[Ma], bcn[Ml+1]; //计数, 分块计数
int ans[Mm];    //答案
void mdf(int pos,int mx) {  //区间转移修改
    int ap = a[pos];
    cnt[ap] += mx;
    if(mx<0 && cnt[ap]==0) {
        --bcn[getB(ap,Ml)];
    } else if(mx>0 && cnt[ap]==mx) {
        ++bcn[getB(ap,Ml)];
    }
}

int main() {
    int n,m;
    qrd(n,m);
    for(int i(1);i<=n;++i) {
        qrd(a[i]);
    }
    nbl = ceil(sqrt(n));
    for(int i(1);i<=m;++i) {
        qrd(aq[i].l,aq[i].r);
        aq[i].i = i;
    }
    sort(aq+1,aq+m+1);
    int l(1), r(0);
    for(int i(1);i<=m;++i) {    //莫队
        Qd& q(aq[i]);
        while(l>q.l) {
            mdf(--l,1);
        }
        while(r<q.r) {
            mdf(++r,1);
        }
        while(l<q.l) {
            mdf(l++,-1);
        }
        while(r>q.r) {
            mdf(r--,-1);
        }
        for(int j(1);j<=Ml;++j) {   //分块暴力查询
            if(bcn[j]!=Ml) {    //若分块中有空位
                int sp = Ml*(j-1);
                for(int k(0);k<Ml;++k) {
                    if(!cnt[sp+k]) {
                        ans[q.i] = sp+k;
                        break;
                    }
                }
                break;
            }
        }
    }
    for(int i(1);i<=m;++i) {
        printf("%d\n",ans[i]);
    }
    return 0;
}