NKOJ 4254 区间MEX （线段树）

发表于 |
字数统计: 910字 | 阅读时长 ≈ 5min

P4254区间MEX

问题描述

给你一个长度为n的数列，元素编号1到n，第i个元素值为Ai。现在有m个形如(L,R)的提问，你需要回答出区间[L,R]的mex值。即求出区间[L,R]中没有出现过的最小的非负整数。

输入格式

第一行，两个整数n和m
第二行，n个空格间隔的整数，表示数列A
接下来m行，每行两个整数L,R,表示一次询问

输出格式

m行，每行一个整数，表示对应询问的答案。

样例输入

7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7

样例输出

3
0
3
2
4

提示

1<=n,m<=200000
0<=Ai<=200000
1<=L<=R<=n

由于没有修改，可以考虑离线算法。先将询问按照左端点排序。

令$S[i]$表示区间$[1,i]$的$MEX值$，容易发现$S[i]$单调不降，并且可以$O(n)$的处理出来$S$数组。那么左端点为1的询问都可以处理，然后考虑如何处理左端点为2时

考虑删掉$A[1]$对$S$数组的影响，那么令$x=A[1]下一次出现的位置$，那么$S[x]$以后肯定不会受到影响，而对于$x$之前的$S[k]$

如果$S[k]>A[i]$，那么$S[k]=A[i]$，否则不变

那么区间修改用线段树来维护，按照左端点升序讨论即可。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define N 200005
#define M 2000005
#define min(a,b) ((a>b)?(b):(a))
using namespace std;
struct node{int id,l,r,ans;}Q[N];
bool cmp(node a,node b)
{return a.l<b.l;}
bool ccp(node a,node b)
{return a.id<b.id;}
int n,m,A[N],B[N],NE[N],LA[N];
bool mark[N];
int ls[M],rs[M],v[M],lazy[M],tot,rt;
int BT(int x,int y)
{
	int p=++tot;
	lazy[p]=-1;
	if(x<y)
	{
		int mid=x+y>>1;
		ls[p]=BT(x,mid);
		rs[p]=BT(mid+1,y);
	}
	else v[p]=B[x];
	return p;
}
void PD(int p)
{
	int l=ls[p],r=rs[p],d=lazy[p];
	lazy[p]=-1;
	v[l]=min(v[l],d);
	v[r]=min(v[r],d);
	if(lazy[l]==-1)lazy[l]=d;
	else lazy[l]=min(lazy[l],d);
	if(lazy[r]==-1)lazy[r]=d;
	else lazy[r]=min(lazy[r],d);
}
void MD(int p,int l,int r,int x,int y,int d)
{
	if(lazy[p]!=-1)PD(p);
	if(x<=l&&y>=r){lazy[p]=d;v[p]=min(v[p],d);return;}
	int mid=l+r>>1;
	if(x<=mid&&y>=l)MD(ls[p],l,mid,x,y,d);
	if(x<=r&&y>mid)MD(rs[p],mid+1,r,x,y,d);
}
int GA(int p,int l,int r,int k)
{
	if(lazy[p]!=-1)PD(p);
	if(l==r)return v[p];
	int mid=l+r>>1;
	if(k<=mid)return GA(ls[p],l,mid,k);
	return GA(rs[p],mid+1,r,k);
}
int main()
{
	int i,x,y;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&A[i]);
	for(i=1;i<=m;i++)scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
	sort(Q+1,Q+m+1,cmp);x=0;
	for(i=1;i<=n;i++)
	{
		mark[A[i]]=1;
		while(mark[x])x++;
		B[i]=x;
	}
	for(i=n;i>=1;i--)
	{
		if(!LA[A[i]])NE[i]=n+1;
		else NE[i]=LA[A[i]];
		LA[A[i]]=i;
	}
	rt=BT(1,n);x=1;i=1;
	while(i<=m)
	{
		while(x<Q[i].l)
		{
			if(x+1<NE[x])MD(rt,1,n,x+1,NE[x]-1,A[x]);
			x++;
		}
		while(x==Q[i].l)
		{
			Q[i].ans=GA(rt,1,n,Q[i].r);
			i++;
		}
	}
	sort(Q+1,Q+m+1,ccp);
	for(i=1;i<=m;i++)printf("%d\n",Q[i].ans);
}