题意：有一个长为n的序列，对其进行q次操作，第i次操作可以把连续的一段覆盖为i
现在给出操作后的序列，第i个数字为a[i]，其中有一些为0的位置可以为任意值，要求构造任意一组合法的操作后的序列
无解输出NO
n,q<=2e5，0<=a[i]<=q
思路：看不懂别人写的题解，照自己的思路写一个……
首先将a[i]从大到小排序，若a[i]已经确定则将a[i]填到i左右两端连续的0中
然后判断q有没有在填完之后的序列中出现，若没有出现则找一段连续的0覆盖成q，找不到0则无解
前面两步能将数列填满，预处理出填完之后数列中每个数值出现的第一次和最后一次出现的位置，如果中间有比他小的数字则不合法
1 #include<cstdio> 2 #include<cstring> 3 #include<string> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<vector> 11 #include<bitset> 12 using namespace std; 13 typedef long long ll; 14 typedef unsigned int uint; 15 typedef unsigned long long ull; 16 typedef pair<int,int> PII; 17 typedef vector<int> VI; 18 #define fi first 19 #define se second 20 #define MP make_pair 21 #define N 210000 22 #define M 51 23 #define MOD 1000000007 24 #define eps 1e-8 25 #define pi acos(-1) 26 #define oo 1e9 27 28 struct node 29 { 30 int x,y; 31 }b[N]; 32 33 int t[N<<1],a[N],c[N],l[N],r[N]; 34 35 bool cmp(node a,node b) 36 { 37 return a.x>b.x; 38 } 39 40 void pushup(int p) 41 { 42 t[p]=min(t[p<<1],t[p<<1|1]); 43 } 44 45 void build(int l,int r,int p) 46 { 47 if(l==r) 48 { 49 t[p]=c[l]; 50 return; 51 } 52 int mid=(l+r)>>1; 53 build(l,mid,p<<1); 54 build(mid+1,r,p<<1|1); 55 pushup(p); 56 } 57 58 int query(int l,int r,int x,int y,int p) 59 { 60 if(x<=l&&r<=y) return t[p]; 61 int mid=(l+r)>>1; 62 int tmp=oo; 63 if(x<=mid) tmp=min(tmp,query(l,mid,x,y,p<<1)); 64 if(y>mid) tmp=min(tmp,query(mid+1,r,x,y,p<<1|1)); 65 return tmp; 66 } 67 68 int main() 69 { 70 int n,q; 71 scanf("%d%d",&n,&q); 72 for(int i=1;i<=n;i++) 73 { 74 scanf("%d",&a[i]); 75 b[i].x=a[i]; 76 b[i].y=i; 77 } 78 for(int i=1;i<=n;i++) c[i]=a[i]; 79 sort(b+1,b+n+1,cmp); 80 for(int i=1;i<=n;i++) 81 if(b[i].x) 82 { 83 int j=b[i].y-1; 84 while(j>0&&c[j]==0) c[j--]=b[i].x; 85 j=b[i].y+1; 86 while(j<=n&&c[j]==0) c[j++]=b[i].x; 87 } 88 int flag=0; 89 for(int i=1;i<=n;i++) 90 if(c[i]==q){flag=1; break;} 91 if(!flag) 92 { 93 int k=0; 94 for(int i=1;i<=n;i++) 95 if(!a[i]){k=i; break;} 96 if(!k) 97 { 98 printf("NO "); 99 return 0; 100 } 101 else 102 { 103 while(k<=n&&a[k]==0) c[k++]=q; 104 } 105 } 106 107 for(int i=1;i<=n;i++) 108 { 109 if(!l[c[i]]) l[c[i]]=i; 110 r[c[i]]=i; 111 } 112 flag=1; 113 build(1,n,1); 114 for(int i=1;i<=q;i++) 115 { 116 int t=oo; 117 if(l[i]<=r[i]&&l[i]&&r[i]) t=query(1,n,l[i],r[i],1); 118 if(t<i){flag=0; break;} 119 } 120 if(flag) 121 { 122 printf("YES "); 123 for(int i=1;i<=n;i++) printf("%d ",c[i]); 124 } 125 else printf("NO "); 126 return 0; 127 }