[CF1023D]Array Restoration

set

题面

有长度为$n$的数列。有$m$次操作。
第$i$次操作中，必须把$[l,r](1\leq l\leq r\leq n)$中所有数字改为$i$。
现在给出疑似最终数列，其中几个数被改成了$0$。回答是否存在初始数列。

• $n,m\leq2*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;
}