自动搬运

查看原文

来自洛谷，原作者为

	disposrestfully **

搬运于2025-08-24 22:24:35，当前版本为作者最后更新于2020-10-21 12:17:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑一个特征对排列的限制,最终小于$val$的数都必须出现在$[l,r]$中,$val$一定不能出现在$[l,r]$中.

把所有数从小到大放到排列里面,设数$x$能放的位置集合是$S(x)$,显然$S(x)$是所有$mex$大于$xs$的区间的交,从中去掉$mex$恰好等于$x$的区间.可以发现$S(x)$要么是$S(x+1)$的子集,要么和$S(x+1)$没有交.所以我们只要在能放的位置里随便找一个放即可.

$O(n)$.

这题的难度定位是“普及组选手能做出来的题”，所以并不需要线段树。下面给出核心代码。

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;
}