题意:刚开始有一长度为\(n\),空白的空数组,有\(q\)次询问,每次询问都会选一个区间\([l,r]\)将其全部涂成颜色i,现在给你一个数组,问你能否得到所给的数组,\(0\)表示任何颜色都可以.

题解:首先这题有一个坑点,数组中必须要有颜色\(q\),然后,易知两个相同颜色之间一定不能有比它小的颜色出现,那么对于\(0\)我们就很容易构造了,如果数组中没有颜色\(q\),就先让一个\(0\)变成\(q\),其他情况只要正反递推让\(0\)等于相邻位置的颜色就好了,因为这样就可以将\(0\)合到一个连续的区间去,一定是最优合法的,剩下的只要用线段树求区间最小值判断是否合法即可.

代码:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
 
int a[N];
vector<int> v[N];
 
struct misaka{
	int l,r;
	int mi=INF;
}tr[N<<2];
 
void push_up(int u){
	tr[u].mi=min(tr[u<<1].mi,tr[u<<1|1].mi);
}
 
void build(int u,int l,int r){
	if(l==r) tr[u]={l,r,a[r]};
	else{
		tr[u]={l,r,INF};
		int mid=(l+r)>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		push_up(u);
	}
}
 
 
int query(int u,int l,int r){
	if(tr[u].l>=l && tr[u].r<=r) return tr[u].mi;
 
	int mid=(tr[u].l+tr[u].r)>>1;
 
	int res1=INF,res2=INF;
	if(l<=mid) res1=query(u<<1,l,r);
	if(r>mid) res2=query(u<<1|1,l,r);
	return min(res1,res2);
}
 
 
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,q;
	cin>>n>>q;
	int mx=0;
	rep(i,1,n){
		cin>>a[i];
		v[a[i]].pb(i);
		mx=max(mx,a[i]);
	}
 
 
	bool flag=true;
	bool ok=false;
	if(mx==q) ok=true;
	rep(i,1,n){
		if(a[i]==0){
			if(!ok){
				a[i]=q;
				ok=true;
			}
			else{
				a[i]=max(a[i-1],a[i+1]);
			}
		}
	}
	per(i,n,1){
		if(a[i]==0){
			a[i]=max(a[i-1],a[i+1]);
		}
	}
	
	build(1,1,n);
 
	rep(i,1,q){
		if(v[i].empty()) continue;
		int n=(int)v[i].size();
		int res=query(1,v[i][0],v[i][n-1]);
		if(res<i) flag=false;
		if(!flag) break;
	}
 
	mx=0;
	rep(i,1,n){
		mx=max(mx,a[i]);
	}
	if(mx!=q) flag=false;
 
	if(flag){
		cout<<"YES\n";
		rep(i,1,n){
			cout<<a[i]<<' ';
		}
	}
	else{
		cout<<"NO\n";
	}
 
 
    return 0;
}