我们知道不满足的肯定是两边大中间小的，这样就用RMQ查询两个相同等值的区间内部最小值即可，注意边界条件
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const long double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double Eps = 1e-;
const int N = 2e5+; int n, q, a[N], t, pre, pos, l[N];
bool vis[N]; const int MAXN = N;
int dp[MAXN][];
int mm[MAXN];
//初始化RMQ, b数组下标从1开始
void initRMQ(int n)
{
mm[] = -;
for(int i = ; i <= n;i++)//
{
mm[i] = ((i&(i-)) == )?mm[i-]+:mm[i-];//推出n在2的多少范围内
dp[i][] = a[i];
}
//RMQ操作求区间最小值
for(int j = ; j <= mm[n];j++)
for(int i = ;i + (<<j) - <= n;i++)
dp[i][j] = min(dp[i][j-],dp[i+(<<(j-))][j-]);
}
//在区间[x, y]查询最大值
int rmq(int x,int y)
{
int k = mm[y-x+];
return min(dp[x][k],dp[y-(<<k)+][k]);
}
int main(void) {
while(cin >> n >> q) {
t = , pos = ;
bool maflag = false;
for(int i = ; i <= n; i++) {
scanf("%d", a + i);
if(a[i] == q)
maflag = true;
if(a[i] == && pos == )
pos = i;
if(a[i] == )
a[i] = a[i-];
if(t == && a[i])//防止全是0
t = a[i];
}
// 都是0
if(t == ) {
printf("YES\n");
for(int i = ; i <= n; i++) {
printf("%d%c", q, i == n ? '\n' : ' ');
}
continue;
}
// 替代前缀0
for(int i = ; i <= n; i++) {
if(a[i] == )
a[i] = t;//相当于全是前导变成与第一个前导相同的
else
break;
}
// 没有出现最大值且有0
if(!maflag && pos) {
a[pos] = q;//最大值赋值给它
maflag = true;
}
if(!maflag) {
printf("NO\n");
continue;
}
// 判断是否重复出现
initRMQ(n);//rmq操作
pre = a[];
bool flag = true;
memset(vis, , sizeof vis);
for(int i = ; i <= n; vis[a[i]] = true, pre = a[i], l[a[i]] = i, i++) {
if(a[i] == pre) //a[i]用过并且令前导为a[i],a[i]的第一个编号是i
continue; //前面和后面一个相同
if(vis[a[i]] && rmq(l[a[i]] + , i - ) < a[i]) {
flag = false;//如果前面已经用过a[i] 用rmq查询这两个之间是最小值如果小于a[i]就不满足
break;
}
}
if(flag) {
printf("YES\n");
for(int i = ; i <= n; i++) {
printf("%d%c", a[i], i == n ? '\n' : ' ');
}
}
else
printf("NO\n");
} return ;
}