Codeforces 1023D

Posted on | In ,

给一个长度为 $n$ 的序列，有 $q$ 次操作，第 $i$ 次操作将区间$[l_i , r_i]$的值赋值为 $i$，后赋值可以覆盖前面的并且保证每个位置都至少会被选一次，现给出最终的序列但某些位置可能被变成了0，问你是否存在满足题意的序列，有的话输出任意一个，没有$NO$ $(1\le n,q \le 2·10^5)$

题解

  • 分析可知三个必须满足的条件：
  • 两个相同的数中间不可能夹着比其小的数
  • $q$必须出现在最后序列中
  • 所以解法也就很显然了
  • 首先随便找个$0$的位置，修改为$q$
  • 记录每个数出现左右端点，从大到小枚举$q$值，线段树查询这个区间的最小值，若最小值为 $0$，把区间$0$都改为这个数，修改后查询最小值是否满足，最后还有$0$的位置，都修改为$1$即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int maxn = 2e5+7;

int n, q, a[maxn], l[maxn], r[maxn], ans[maxn];
bool flag;


struct node
{
    int l, r, minx, k;
}t[maxn<<2];


void init()
{
    flag=false;
    for(int i=0;i<=200000;i++)
    {
        l[i]=maxn;
        r[i]=0;
    }
}

void build(int x,int l,int r)
{
    t[x].l=l, t[x].r=r;
    if(l==r)
    {
        t[x].minx=t[x].k=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(x<<1, l, mid);
    build(x<<1|1, mid+1, r);
    t[x].minx=min(t[x<<1].minx, t[x<<1|1].minx);
}

void update(int x, int val)
{
    int l=t[x].l, r=t[x].r;
    if(l==r)
    {
        ans[l]=val;
        t[x].minx=t[x].k=val;
        return;
    }
    int mid=(l+r)/2;
    if(t[x<<1].minx==0) update(x<<1,  val);
    if(t[x<<1|1].minx==0) update(x<<1|1, val);
    t[x].minx=min(t[x<<1].minx, t[x<<1|1].minx);
}

int query(int x,int ql,int qr, int val)
{
    int l=t[x].l, r=t[x].r;
    if(ql<=l && qr>=r)
    {
        if(t[x].minx==0)
        {
            update(x,val);
        }
        return t[x].minx;
    }
    int mid=(l+r)/2;
    int ans = maxn+10;
    if(ql<=mid) ans = min(ans, query(x<<1, ql, qr, val));
    if(qr>mid)  ans = min(ans, query(x<<1|1, ql,qr, val));
    return ans;
}


int main()
{
    scanf("%d%d", &n, &q);
    init();
    for(int i=1;i<=n;i++)
    {
        scanf("%d" , &a[i]);
        ans[i]=a[i];
        l[a[i]]=min(l[a[i]], i);
        r[a[i]]=max(r[a[i]], i);
    }
    build(1, 1, n);
    if(l[q] == maxn)
    {
        if(l[0] == maxn)
        {
            puts("NO");
            return 0;
        }
        else
        {
            a[l[0]]=q;
            ans[l[0]]=q;
        }
    }
    build(1, 1, n);
    for(int i=q;i>=1;i--)
    {
        if(l[i] != maxn)
        {
            if(query(1, l[i], r[i], i)< i)
            {
                puts("NO");
                return 0;
            }
        }
    }
    puts("YES");
    for(int i=1;i<=n;i++)
    {
        if(ans[i]==0) ans[i]=1;
        printf("%d ", ans[i]);
    }
    return 0;
}