题目概述

按顺序将 $1\sim q$ 涂到长度为 $n$ 的板上（范围自定），问是否能够涂成目标状态（目标状态中有些通配符）。

解题报告

被翰爷秒掉了，目标状态中相邻两个相同颜色之间肯定被涂过该颜色，所以线段树覆盖一下，如果某个点被比自己大的颜色覆盖了就违法了。如果是通配的话就直接给覆盖最大值，如果没有被覆盖就给 $1$ 。最后注意一下 $q$ 有没有用过就行了，如果没用用过就随便塞给一个通配，如果没有通配就gg。

示例程序

翰爷友情（并不）提供代码。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000005;
int N_seg,ch[maxn*2][2],Max[maxn*2];
int Build(int L,int R){
  int p=++N_seg;
  if(L==R) return p;
  int mid=(L+R)>>1;
  ch[p][0]=Build(L,mid); ch[p][1]=Build(mid+1,R);
  return p;
}
void Update(int p,int L,int R,int qL,int qR,int val){
  if(R<qL||qR<L) return;
  if(qL<=L&&R<=qR) return Max[p]=max(Max[p],val),void();
  int mid=(L+R)>>1;
  Update(ch[p][0],L,mid,qL,qR,val); Update(ch[p][1],mid+1,R,qL,qR,val);
}
int res=0;
void Query(int p,int L,int R,int pos){
  if(pos<L||R<pos) return;
  res=max(res,Max[p]); if(L==R) return;
  int mid=(L+R)>>1;
  Query(ch[p][0],L,mid,pos); Query(ch[p][1],mid+1,R,pos);
}
int n,Q,a[maxn],lst[maxn];
int main(){
  scanf("%d%d",&n,&Q);
  bool hasQ=false;
  for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    hasQ|=(a[i]==Q);
  }
  Build(1,n);
  for(int i=1;i<=n;i++){
    if(!a[i]) continue;
    if(lst[a[i]]){
      Update(1,1,n,lst[a[i]],i,a[i]);// printf("[%d %d] %d\n",lst[a[i]],i,a[i]);
    }
    lst[a[i]]=i;
  }
  for(int i=1;i<=n;i++){
    res=0; Query(1,1,n,i);
    if(!a[i]){
      if(!hasQ){ a[i]=Q; hasQ=true; } else
      if(!res) a[i]=1; else a[i]=res;
    }
    else if(a[i]<res) return puts("NO"), 0;
  }
  if(!hasQ) return puts("NO"), 0;
  puts("YES");
  for(int i=1;i<=n;i++) printf("%d ",a[i]);
  return 0;
}