[BZOJ3585][BZOJ3339]mex

[BZOJ3585][BZOJ3339]mex

试题描述

有一个长度为n的数组{a1,a2,...,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。

输入

第一行n,m。
第二行为n个数。
从第三行开始，每行一个询问l,r。

输出

一行一个数，表示每个询问的答案。

输入示例

输出示例

数据规模及约定

对于100%的数据：
1<=n,m<=200000
0<=ai<=10
1<=l<=r<=n

题解

首先离线，将询问按右端点排序。然后我们就可以从左到右一个个添加序列中的数了。现在我们可以认为右端点固定为 R 了，考虑一个数 i，我们只关心左边离它最近的位置，不妨称为 lstp[i]，那么 mex{ A[L..R] } = k 等价于 min{ lstp[0..k-1] } ≥ L，即小于 k 的数上一次出现的位置在 L 及之后，即 [L, R] 中包含了所有 0 到 k-1 中的数字。这样，我们维护一个权值线段树，支持点修改，在查询时可以直接在线段树上二分。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

using namespace std;

int read() {

	int x = 0, f = 1; char c = getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

	return x * f;

}

#define maxn 200010

#define maxnode 6000010

#define maxv 1000000000

int n, q, A[maxn], num[maxn];

struct Que {

	int l, r, id;

	Que() {}

	Que(int _1, int _2, int _3): l(_1), r(_2), id(_3) {}

	bool operator < (const Que& t) const { return r < t.r; }

} qs[maxn];

int ToT, mnv[maxnode], lc[maxnode], rc[maxnode], rt;

void update(int& o, int l, int r, int val, int npos) {

	if(!o) o = ++ToT;

	if(l == r) mnv[o] = npos;

	else {

		int mid = l + r >> 1;

		if(val <= mid) update(lc[o], l, mid, val, npos);

		else update(rc[o], mid + 1, r, val, npos);

		mnv[o] = min(mnv[lc[o]], mnv[rc[o]]);

	}

	return ;

}

int query(int lim) {

	int l = 0, r = maxv, o = rt;

	while(l < r) {

		if(!o) return l;

		int mid = l + r >> 1;

		if((lc[o] ? mnv[lc[o]] : 0) >= lim) l = mid + 1, o = rc[o];

		else r = mid, o = lc[o];

	}

	return l;

}

int Ans[maxn];

int main() {

	n = read(); q = read();

	for(int i = 1; i <= n; i++) A[i] = read();

	for(int i = 1; i <= q; i++) {

		int l = read(), r = read();

		qs[i] = Que(l, r, i);

	}

	sort(num + 1, num + n + 1);

	sort(qs + 1, qs + q + 1);

	for(int i = 1, j = 1; i <= q; i++) {

		while(j <= qs[i].r) update(rt, 0, maxv, A[j], j), j++;

		Ans[qs[i].id] = query(qs[i].l);

	}

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

	return 0;

}