抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

P4137 Rmq Problem / mex

发布于：2019年8月8日

传送门

首先建议看一下这篇博客，学习一下回滚莫队和撤销的奇巧淫技。

0≤ai≤1090 \le a_i \le 10^9，蜃是恐怖，但是发现如果答案ans>n+1ans > n+1，说明1...n+11 ... n+1所有数都出现过，但是我们只有nn个数，所以矛盾，于是读入的时候这样处理即可。

1
a[i]=min(n+1,read());

加入一个数，如何维护mexmex值呢？

按照上面的思路，维护一个Max[i]Max[i]数组（其中ii为连续11的端点时Max[i]Max[i]才有意义）代表连续11的另一个端点的下标。

如果包含现在数字的连续11的左端点能到达00，说明现在的mexmex值为右端点+1+1

1
if (L==0) ans=R+1;

注意当加入的数为00的时候有一个小特判，为了防止x−1x-1越界。

时间复杂度为O(nn)O(n \sqrt n)，但是它就是被卡了，交几次说不定能过呢？

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>
#define MAXN 2000005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN],pos[MAXN],n,m;
struct Query{
    int l,r,id;
}q[MAXN];
inline bool operator < (const Query &A,const Query &B){
    return pos[A.l]==pos[B.l]?A.r<B.r:pos[A.l]<pos[B.l];
}
static int Ans[MAXN];
static int vis[MAXN];
static int Max[MAXN];//最重要的数组，存的是这一段的另一个端点
int ans,Size;
struct node{
    int pos,org;//位置，一开始的值
}stk[MAXN];
int top,f;
inline void Update(int pos,int val){
    if (f) stk[++top]=node{pos,Max[pos]};
    Max[pos]=val;
}
inline void Add(int x){
    vis[x]++;
    if (vis[x]>1) return ;
	if (x==0) {//特判 
		if (!vis[x+1]) ans=x+1;
		else ans=Max[x+1]+1;
		int R=Max[x+1];
		Update(0,R);Update(R,0);
		return ;
	}
    int L=vis[x-1]?Max[x-1]:x,R=vis[x+1]?Max[x+1]:x;
    if (L==0) ans=R+1;
    Update(L,R);Update(R,L);
}
inline void Undo(){
    for (register int i=top;i>=1;--i){
        Max[stk[i].pos]=stk[i].org;
    }
    top=0;
}
inline int BruteForce(int l,int r){
    ans=0;
    f=false;
    for (register int i=l;i<=r;++i){
        Add(a[i]);
    }
    for (register int i=l;i<=r;++i){
        Max[a[i]]=0,vis[a[i]]=0;
    }
    int temp=ans;
    ans=0;
    return temp;
}
inline int MoQueue(int i,int id){
    int R=min(n,Size*id);
    int l=R,r=R-1;
    ans=0;
    memset(vis,0,sizeof(vis));
    memset(Max,0,sizeof(Max));
    top=0;
    while (pos[q[i].l]==id){
        if (pos[q[i].l]==pos[q[i].r]){
            Ans[q[i].id]=BruteForce(q[i].l,q[i].r);
            i++;
            continue;
        }
        f=false;
        while (r<q[i].r) Add(a[++r]);
        int temp=ans;
        f=true;
        while (l>q[i].l) Add(a[--l]);
        Ans[q[i].id]=ans;
        while (l<R) vis[a[l++]]--;
        Undo();
        ans=temp;
        i++;
    }
    return i;
}
int main(){
    n=read(),m=read();
    Size=(int)(n/sqrt(m));
    for (register int i=1;i<=n;++i){
        a[i]=min(n+1,read());
        pos[i]=(i-1)/Size+1;
    }
    for (register int i=1;i<=m;++i){
        q[i].l=read(),q[i].r=read(),q[i].id=i;
    }
    sort(q+1,q+1+m);
    int ptr=1;
    for (register int i=1;i<=pos[n];++i){
        ptr=MoQueue(ptr,i);
    }
    for (register int i=1;i<=m;++i){
        printf("%d\n",Ans[i]);
    }
}

8/11 upd

其实是我之前愚蠢了，其实不要用只插入的莫队，要用只删除的莫队

因为mexmex这个东西有很神奇的特性，你插入的时候不能O(1)O(1)得出mexmex，但是删除的时候，如果这个数的cntcnt被减至00，那么你的答案就和它取一个min⁡\min即可。

于是使用只删除的莫队，以左端点所在的块编号为第一关键字升序排列，以右端点为第二关键字降序排列，然后预处理出LL到q[i].rq[i].r的cntcnt 数组（q[i].rq[i].r 是这一段右端点的最大值），每次删除即可。

代码和思维上面都比较好想。

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
#include <bits/stdc++.h>
#define MAXN 2000005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN],pos[MAXN],n,m,Size;
static int Ans[MAXN];
struct Query{
    int l,r,id;
}q[MAXN];
inline bool operator < (const Query &A,const Query &B){
    return pos[A.l]==pos[B.l]?A.r>B.r:pos[A.l]<pos[B.l];
}
static int vis[MAXN],bf[MAXN];
inline int BruteForce(int l,int r){
    for (register int i=l;i<=r;++i){
        bf[a[i]]++;
    }
    int pos=-1;
    while (bf[++pos]);
    for (register int i=l;i<=r;++i){
        bf[a[i]]=0;
    }
    return pos;
}
inline int MoQueue(int i,int id){
    int L=(id-1)*Size+1,R=min(id*Size,n);
    memset(vis,0,sizeof(vis));
    for (register int j=L;j<=q[i].r;++j){
        vis[a[j]]++;
    }
    int r=q[i].r;
    int ans=-1;
    while (vis[++ans]);
    for (;pos[q[i].l]==id;++i){
        if (pos[q[i].l]==pos[q[i].r]){
            Ans[q[i].id]=BruteForce(q[i].l,q[i].r);
            continue;
        }
        for (register int j=r;j>q[i].r;--j){
            if (--vis[a[j]]==0) ans=min(ans,a[j]);
        }
        r=q[i].r;
        int temp=ans;
        for (register int j=L;j<q[i].l;++j){
            if (--vis[a[j]]==0) ans=min(ans,a[j]);
        }
        Ans[q[i].id]=ans;
        for (register int j=L;j<q[i].l;++j){
            ++vis[a[j]];
        }
        ans=temp;
    }
    return i;
}
int main(){
    n=read(),m=read();
    Size=(int)(n/sqrt(m));
    for (register int i=1;i<=n;++i){
        a[i]=min(n+1,read());
        pos[i]=(i-1)/Size+1;
    }
    for (register int i=1;i<=m;++i){
        q[i].l=read(),q[i].r=read(),q[i].id=i;
    }
    sort(q+1,q+1+m);
    int ptr=1;
    for (register int i=1;i<=pos[n];++i){
        ptr=MoQueue(ptr,i);
    }
    for (register int i=1;i<=m;++i){
        printf("%d\n",Ans[i]);
    }
}
相关文章
AT1219 歴史の研究BZOJ 4358 permuP1903 [国家集训队]数颜色 / 维护队列P3674 小清新人渣的本愿基本概念

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gaisaiyuno.github.io/archives/1e45153c.html

更新于：2022年6月14日

题解

莫队

回滚莫队

评论