【回滚莫队】mex
2021-05-11 11:53:00 # ACM

题链

多次询问一个区间内最小没有出现过的自然数

回滚莫队：发现添加一个数难以维护，故只用删除操作来维护答案。用$cnt[]$来计数，一开始把$[1,n]$全部塞进去，记录全局答案$ANS$，只有新的询问所属的块与上次询问不同时更新$ANS$（因为该询问前面的块已经没有用了）；

什么时候更新答案$ans$呢？一开始$ans = ANS$的，每一次删除的时候，判断$cnt[x]$是否等于$0$，因为一开始$cnt[]$数组是记录了 $[$ 询问左区间的块的左区间$,n]$ 之间的所有数字的，所以删着删着如果$cnt[x] == 0$了，那么$ans = min(ans,x)$；

详细看代码；

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define Pair pair<LL,LL>
#define f1 first
#define f2 second
#define ls rt<<1
#define rs rt<<1|1
#define Pi acos(-1.0)
#define eps 1e-6
#define DBINF 1e100
#define mod 998244353
#define MAXN 1e18
#define MS 1000009

LL n,m;
LL a[MS]; // 原数组 
struct node{
	int l,r,id;
}ask[MS];
LL size,bknum; // 每一块的位置，总块数 
LL bkl[MS],bkr[MS]; // 分别记录第i块的左右区间 
LL belong[MS]; // 表示下标pos位置所属块号 

LL ANS;
LL cnp[MS]; // 临时计数数组 用于暴力处理 cnp[i]表示i出现次数 
LL cnt[MS]; // 用于计数数组 cnt[i]表示i出现次数 

LL ac[MS]; // 记录答案 

void init_ANS(){
	for(int i=1;i<=n;i++){
		if(a[i] > n+1) continue;
		cnt[a[i]]++;
	}
	while(cnt[ANS]) ANS++;
}

void init_bk(){
	size = sqrt(n);
	bknum = n/size;
	for(int i=1;i<=bknum;i++){
		bkl[i] = (i-1)*size+1;
		bkr[i] = i*size; 
	}
	if(bkr[bknum] < n){
		bknum++;
		bkl[bknum] = bkr[bknum-1]+1;
		bkr[bknum] = n;
	}
	for(int i=1;i<=bknum;i++){
		for(int j=bkl[i];j<=bkr[i];j++){
			belong[j] = i;
		}
	}
}

bool cmp(node t1,node t2){ // 按块排序，左区间从小到大，右区间从大到小 
	if(belong[t1.l] != belong[t2.l]) return t1.l < t2.l;
	return t1.r > t2.r;
}

void add(int pos){ 
	if(a[pos] > n+1) return;
	cnt[a[pos]]++;
}

void remove(int pos,LL &ans){ // 删除时更新答案 
	if(a[pos] > n+1) return;
	cnt[a[pos]]--;
	if(cnt[a[pos]] == 0) ans = min(ans,a[pos]);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	init_ANS(); // 初始化全局答案 
	for(int i=1;i<=m;i++){
		int l,r;
		cin >> l >> r;
		ask[i] = {l,r,i};
	}
	init_bk(); // 初始化 块 
	sort(ask+1,ask+m+1,cmp); // 对询问按 块 排序 
	
	int L = 1 ,R = n;
	int lastbk = 0;
	LL ans = ANS;
	for(int i=1;i<=m;i++){
		if(belong[ask[i].l] == belong[ask[i].r]){ // 属于同一块 暴力处理 
			for(int j=ask[i].l;j<=ask[i].r;j++){
				if(a[j] > n+1) continue;
				cnp[a[j]]++;
			}
			LL tmp = 0;
			while(cnp[tmp]) tmp++;
			ac[ask[i].id] = tmp;
			for(int j=ask[i].l;j<=ask[i].r;j++){
				if(a[j] > n+1) continue;
				cnp[a[j]]--;
			}
			continue;
		}
		if(belong[ask[i].l] != lastbk){ // 新的左区间与上次的左区间块不同 
			while(R < n) add(++R);
			while(L < bkl[belong[ask[i].l]]) remove(L++,ANS); // ***更新全局ANS 
			lastbk = belong[ask[i].l];
			ans = ANS;
		}
		while(R > ask[i].r){
			remove(R--,ans);
		}
		LL tmp = ans; // 左区间可能是乱序的，tmp作为临时记录 
		while(L < ask[i].l){
			remove(L++,tmp);
		}
		ac[ask[i].id] = tmp;
		// 回滚 
		while(L > bkl[belong[ask[i].l]]) add(--L);
	}
	for(int i=1;i<=m;i++){
		cout << ac[i] << "\n";
	}
	
	return 0;
}
Prev
2021-05-11 11:53:00 # ACM
Next