题目大意:给你一个数组,数组是经过q次区间覆盖后的结果,第i次覆盖是把区间内的值赋值为i,其中有若干个地方数值未知(就是0),让你判断这个数组是否可以经过覆盖后得到的,如果可以,输出任意一种可行数组。

思路:不合法的情况只有2种。1:两个相同的数字中间出现了比它小的数字,比如: 6 5 6 就不合法,因为覆盖6的时候是覆盖连续的一段区间,而5比6先覆盖,所以这种情况不存在。我赛后看AC代码的时候发现有的人只是判断是否出现谷形的情况,这种是不对的。

比如这种样例:3 3 3 1 2 这种判断方法会输出NO,但实际上却可以覆盖。那么怎么找任意区间内的最小值呢?线段树啊(比赛结束前10分钟才想到。。。)。

2:最大值没出现过而且没有0,因为最大值是最后一次覆盖的,所以肯定有最大值。

那么我们就可以写代码了:

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<string>
#include<map>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#define INF 0x3f3f3f3f
#define LL long long
#define mk(a,b) make_pair(a,b)
#define pii pair<int,int>
using namespace std;
const int maxn=200010;
map<int,int> mp;
int a[maxn],mi[maxn];
bool vis[maxn];
int minv[4*maxn];
int ql,qr;
int query(int o,int l,int r){//查询最小值
int mid=l+(r-l)/2,ans=INF;
if(ql<=l&&r<=qr)return minv[o];
if(ql<=mid)ans=min(ans,query(o*2,l,mid));
if(mid<qr)ans=min(ans,query(o*2+1,mid+1,r));
return ans;
}
void build(int o,int l,int r){
if(l==r){
minv[o]=a[l];
return;
}
int mid=l+(r-l)/2;
build(o*2,l,mid);
build(o*2+1,mid+1,r);
minv[o]=min(minv[o*2],minv[o*2+1]);
}
int main(){
int n,m,mi=INF,mx=0,cnt=0;
bool flag=1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
mx=max(mx,a[i]);
if(a[i]==0){//为了方便建线段树,把0赋值为INF
a[i]=INF;
cnt++;
}
}
if(mx<m&&cnt==0){//第二种情况
printf("NO\n");
return 0;
}
build(1,1,n);//建树
for(int i=1;i<=n;i++){
if(a[i]==INF){
continue;
}
if(vis[a[i]]){//如果之前出现过
ql=mp[a[i]],qr=i;
if(query(1,1,n)<a[i]){//如果小于a[i]值
flag=0;
break;
}
}
vis[a[i]]=1;
mp[a[i]]=i;
}
if(flag==0){//情况1
printf("NO\n");
return 0;
}
for(int i=1,j;i<=n;i++){//从前往后扫一遍
if(a[i]!=INF)continue;
else{
if(mx<m)a[i]=m;//如果最大值没出现,就赋值为最大值
else a[i]=a[i-1];//否则赋值为他前面的值
mx=max(mx,a[i]);
}
}
for(int i=n,j;i>=1;i--){
if(a[i]!=INF&&a[i]!=0)continue;//防止a[1]为0的情况
else{
if(mx<m)a[i]=m;
else a[i]=a[i+1];
mx=max(mx,a[i]);
}
}
printf("YES\n");
for(int i=1;i<=n;i++)
printf("%d ",a[i]);
}

  

最新文章

  1. 十二. 一步步破解JEB 2.0demo版二
  2. .NET Lambda
  3. 【语言基础】c++ 基本数据类型与字节数组(string,char [] )之间的转化方法
  4. Eclipse的link方式安装JBPM6插件(JBPM学习之一)
  5. php 修改上传文件大小 (max_execution_time post_max_size)
  6. 烂泥:ubuntu安装KVM虚拟机管理virt-manager
  7. Mysql基础语法
  8. 开源HTML5 Canvas游戏Runtime发布
  9. Java-马士兵设计模式学习笔记-命令模式
  10. Centos与win8.1的双系统
  11. Poetize6: IncDec Sequence
  12. 一款好看+极简到不行的HTML5音乐播放器-skPlayer
  13. 原生JS研究:学习jquery源码,收集整理常用JS函数
  14. Python中模块之queue的功能介绍
  15. 安卓高级3 RecyclerView结合SwipeRefreshLayout并添加上拉
  16. SQL Server 检测到基于一致性的逻辑 I/O 错误 pageid 不正确
  17. 请根据英文单词的第一个字母判断星期几,如果第一个字母是一样的,则继续判断第二个字母。例如如果第一个字母是S,则继续判断第二个字母,如果第二个字母是a,则输出“星期六”
  18. 嵌入式Linux学习(一)
  19. TNS
  20. [Python] 正确复制列表的方法

热门文章

  1. 强制关闭iPhone iPad AppleWatch MacOS
  2. Git_学习_09_指定某些文件不上传
  3. 【转】Python获取当前系统时间
  4. freemarker实现第一个HelloWorld
  5. Python函数-round() 函数
  6. Linux 命令行监视显卡使用情况
  7. BZOJ3289:Mato的文件管理
  8. c++11之三: sizeof运算符 auto的优势 __func__预定义标识符
  9. Azure CLI的Query
  10. Common 通用类库