我们知道不满足的肯定是两边大中间小的，这样就用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-7; const int N = 2e5+9; int n, q, a[N], t, pre, pos, l[N]; bool vis[N]; const int MAXN = N; int dp[MAXN][20]; int mm[MAXN]; //初始化RMQ, b数组下标从1开始 void initRMQ(int n) { mm[0] = -1; for(int i = 1; i <= n;i++)// { mm[i] = ((i&(i-1)) == 0)?mm[i-1]+1:mm[i-1];//推出n在2的多少范围内 dp[i][0] = a[i]; } //RMQ操作求区间最小值 for(int j = 1; j <= mm[n];j++) for(int i = 1;i + (1<<j) -1 <= n;i++) dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } //在区间[x, y]查询最大值 int rmq(int x,int y) { int k = mm[y-x+1]; return min(dp[x][k],dp[y-(1<<k)+1][k]); } int main(void) { while(cin >> n >> q) { t = 0, pos = 0; bool maflag = false; for(int i = 1; i <= n; i++) { scanf("%d", a + i); if(a[i] == q) maflag = true; if(a[i] == 0 && pos == 0) pos = i; if(a[i] == 0) a[i] = a[i-1]; if(t == 0 && a[i])//防止全是0 t = a[i]; } // 都是0 if(t == 0) { printf("YES\n"); for(int i = 1; i <= n; i++) { printf("%d%c", q, i == n ? '\n' : ' '); } continue; } // 替代前缀0 for(int i = 1; i <= n; i++) { if(a[i] == 0) 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[1]; bool flag = true; memset(vis, 0, sizeof vis); for(int i = 1; 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]] + 1, i - 1) < a[i]) { flag = false;//如果前面已经用过a[i] 用rmq查询这两个之间是最小值如果小于a[i]就不满足 break; } } if(flag) { printf("YES\n"); for(int i = 1; i <= n; i++) { printf("%d%c", a[i], i == n ? '\n' : ' '); } } else printf("NO\n"); } return 0; }