题解 P6852 【Mex】
disposrestfully
·
·
题解
考虑一个特征对排列的限制,最终小于val的数都必须出现在[l,r]中,val一定不能出现在[l,r]中.
把所有数从小到大放到排列里面,设数x能放的位置集合是S(x),显然S(x)是所有mex大于xs的区间的交,从中去掉mex恰好等于x的区间.可以发现S(x)要么是S(x+1)的子集,要么和S(x+1)没有交.所以我们只要在能放的位置里随便找一个放即可.
这题的难度定位是“普及组选手能做出来的题”，所以并不需要线段树。下面给出核心代码。
```cpp
int main(){
n=read(),m=read();
for (int i=0;i<=n;++i)
pl[i]=0,pr[i]=n,ql[i]=n,qr[i]=0;
for (int i=1;i<=m;++i){
int l=read(),r=read(),val=read();
if (val){
pl[val-1]=max(pl[val-1],l);
pr[val-1]=min(pr[val-1],r);
}else ++s[l],--s[r+1];
ql[val]=min(ql[val],l);
qr[val]=max(qr[val],r);
}
for (int i=1;i<=n;++i) s[i]+=s[i-1];
for (int i=n-1;i>=0;--i){
pl[i]=max(pl[i],pl[i+1]);
pr[i]=min(pr[i],pr[i+1]);
if (pl[i]>pr[i]) return puts("-1"),0;
}
for (int i=pl[0];i<=pr[0];++i)
if (!s[i]) sta.push_back(i),vis[i]=1;
if (sta.empty()) return puts("-1"),0;
ans[sta.back()]=0,sta.pop_back();
for (int i=pl[0];i<=pr[0];++i)
if (!vis[i]) sta.push_back(i),vis[i]=1;
for (int i=1;i<=n;++i){
if (ql[i]<=qr[i]){
for (int j=pl[i];j<ql[i] && j<=pr[i] && !vis[j];++j)
sta.push_back(j),vis[j]=1;
for (int j=pr[i];j>qr[i] && j>=pl[i] && !vis[j];--j)
sta.push_back(j),vis[j]=1;
}
if (sta.empty() || (sta.back()>=ql[i] && sta.back()<=qr[i]))
return puts("-1"),0;
ans[sta.back()]=i,sta.pop_back();
for (int j=max(pl[i],ql[i]);j<=pr[i] && !vis[j];++j)
sta.push_back(j),vis[j]=1;
for (int j=min(pr[i],qr[i]);j>=pl[i] && !vis[j];--j)
sta.push_back(j),vis[j]=1;
}
for (int i=0;i<=n;++i)
printf("%d ",ans[i]);
puts("");
return 0;
}
```