https://www.zybuluo.com/ysner/note/1255832
题面
有长度为(n)的数列。有(m)次操作。
第(i)次操作中，必须把([l,r](1leq lleq rleq n))中所有数字改为(i)。
现在给出疑似最终数列，其中几个数被改成了(0)。回答是否存在初始数列。
- (n,mleq2*10^5)
解析
很显然的是，如果两个相同数之间存在比它们小的数，这个序列一定不合法。
同样，如果这个序列不存在值为(m)的数，这个序列也不合法。
思考怎么填数。
首先，如果没有数列中没有数字(m)，优先填(m)。
其次，设数(x)分别在该位左右两边存在，则该位应取(max{x})。
再次，如果不存在(x)，该位填(1)。（因为绝对合法，且不可能干扰到其它位的填数）
然后想怎么维护这个(max{x})。
考虑弄个(set)维护(x)，所有(x)的第一个出现时，(insert(x))；所有(x)的最后一个出现时，(erase(x))。
可删除大根堆也可以，只是写着麻烦。
还有，取(set)中最后一个数可以用*--Q.end()，end不会真的自减。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=45989,N=5e5+100;
int n,m,top,a[N],L[N],R[N],mx,mn;
set<int>Q;
set<int>::iterator it;
il int gi()
{
re int x=0,t=1;
re char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
int main()
{
n=gi();m=gi();
fp(i,1,n) a[i]=gi(),mx=max(mx,a[i]),mn=min(mn,a[i]);
fq(i,n,1) if(!R[a[i]]) R[a[i]]=i;
fp(i,1,n) if(!L[a[i]]) L[a[i]]=i;
fp(i,1,n)
{
if(a[i]==0)
{
if(mx<m) a[i]=m,mx=m;
else if(Q.size()) a[i]=*--Q.end();
else a[i]=1;
}
else
{
if(L[a[i]]==i&&L[a[i]]<R[a[i]]) Q.insert(a[i]);
if(R[a[i]]==i&&L[a[i]]<R[a[i]]) Q.erase(a[i]);
if(Q.size()) if(a[i]<(*--Q.end())) {puts("NO");return 0;}
}
}
if(mx<m) {puts("NO");return 0;}
puts("YES");
fp(i,1,n) printf("%d ",a[i]);puts("");
return 0;
}