【解题报告】洛谷P6852 Mex

题目链接

https://www.luogu.com.cn/problem/P6852

思路

要求构造一个序列

我们发现，对于一个区间 \([l,r]\) 的 \(mex\) 为 \(val\) ，\([0,val-1]\) 必须都出现在这个区间中，并且 \(val\) 不能出现在这个区间中

所以我们对于某个值

• \(val=0\)

可以变成这个 \(val\) 必须出现的 一个区间，和不能出现的很多区间

• \(val \not =0\)

可以变成一个必须出现的区间和不能出现的区间，实际上就是把不能出现的区间并起来，剩下的就是能出现的区间了

所以我们从小到大填入一个数字 \(val\) ,每次在 \(val\) 必须出现的区间中随便选一个点填进去

然后我们用一个集合来维护可以选择的点，每次用二分确定还能选择符合要求的数字，且必须在区间的左端点，然后再判断它是不是在不能出现的区间里面，如果不在的话，填进去，否则不填进去，然后找不在这个区间只能的能填进去的下一个位置，然后重复上述步骤即可

我们特判一下 \(0\) 的位置，然后就解决了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <set>
using namespace std;
const int maxn=500005;
int n,m;
int loc[maxn],roc[maxn];
int lb[maxn],rb[maxn];
int pre[maxn],ans[maxn];
bool flag;
set <int> s;
int main()
{
	cin>>n>>m;
	for(int i=0;i<=n;i++)
	s.insert(i);
	for(int i=0;i<=n+1;i++)
	{
		loc[i]=0,roc[i]=n;
		lb[i]=n+1,rb[i]=-1;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,val;
		cin>>x>>y>>val;
		if(val)
		{
			loc[val-1]=max(loc[val-1],x);
			roc[val-1]=min(roc[val-1],y);
			lb[val]=min(lb[val],x),rb[val]=max(rb[val],y);
		}
		else
		{
			pre[x]++;
			pre[y+1]--;
		}
	}
	for(int i=n;i>=0;i--)
	{
		loc[i]=max(loc[i],loc[i+1]);
		roc[i]=min(roc[i],roc[i+1]);
	}
	for(int i=0;i<=n;i++)
	{
		pre[i]+=pre[i-1];
		if(loc[0]<=i&&i<=roc[0]&&pre[i]==0)
		{
			ans[i]=0;
			s.erase(i);
			break;
		}
	}
	for(int i=1;i<=n;i++)
	{
		set <int>::iterator it=s.lower_bound(loc[i]);
		if(it!=s.end()&&*it<=roc[i]&&(lb[i]>*it||*it>rb[i]))
		{
			ans[*it]=i;
			s.erase(it);
		}
		else if(rb[i]!=-1)
		{
			it=s.lower_bound(rb[i]+1);
			if(it!=s.end()&&*it<=roc[i])
			{
				ans[*it]=i;
				s.erase(it);
			}
		}
	}
	if(s.size())
	cout<<-1<<'\n';
	else
	{
		for(int i=0;i<=n;i++)
		cout<<ans[i]<<" ";
		cout<<'\n';
	}
	return 0;
}