BZOJ3585/洛谷P4137 区间mex（主席树）

题意

有 $n$n 个数 $\{a_n\}${an​}，有 $m$m 个询问，每个询问给定 $l,r$l,r，求 $a_l,...,a_r$al​,...,ar​ 的 $mex$mex。（最小的未出现的自然数）
其中 $n,m\leq 2e5,a_i\leq10^9$n,m≤2e5,ai​≤109

分析

令 $v_i$vi​ 表示 $i$i 最后出现的位置。用主席树维护 $v_i$vi​。
那么对于一个询问 $(l,r)$(l,r)，我们在 $[1,r]$[1,r] 中的权值线段树上二分第一个比 $l$l 小的数的位置即可，二分可以通过维护最小值来解决。
时空复杂度 $O(nlogV)$O(nlogV)。

代码如下

#include <bits/stdc++.h>
#define lson l, m, lch[rt]
#define rson m + 1, r, rch[rt]
using namespace std;

int read(){
	int x, f = 1;
	char ch;
	while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
	x = ch - '0';
	while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
	return x * f;
}


const int N = 200005;
int cnt, lch[N * 33], rch[N * 33], val[N * 33], root[N], las[N];

void update(int l, int r, int &rt, int las, int p, int c){
	rt = ++cnt;
	lch[rt] = lch[las], rch[rt] = rch[las];
	if(l == r){
		val[rt] = c;
		return;
	}
	int m = l + r >> 1;
	if(p <= m) update(lson, lch[las], p, c);
	else update(rson, rch[las], p, c);
	val[rt] = min(val[lch[rt]], val[rch[rt]]);
}

int query(int l, int r, int rt, int k){
	if(l == r) return l;
	int m = l + r >> 1;
	if(val[lch[rt]] >= k) return query(rson, k);
	return query(lson, k);
}

int main(){
	int i, j, n, m, a, b;
	n = read(); m = read();
	for(i = 1; i <= n; i++) j = read(), update(0, 1e9, root[i], root[i - 1], j, i);
	for(i = 1; i <= m; i++){
		a = read(); b = read();
		printf("%d\n", query(0, 1e9, root[b], a));
	}
	return 0;
}