CF 1023D Array Restoration - 线段树

题解

非常容易想到的线段树， 还可以用并查集来。 还有一位大神用了$O(n)$ 就过了Orz

要判断是否能染色出输入给出的序列，必须满足两个条件：

1、 序列中必须存在一个$q$

2、 两个相同的数$x$的中间不存在比 $ x$ 小的数

首先判断输入的数列中是否存在$q$， 若不存在$q$ 且没有 $a_i = 0$， 表示序列中一定没有$q$， 直接输出NO

　　若存在某个$a_i = 0$ ， 将任意一个染成$q$即可

然后我们再查询两个相同的数$x$ 中是否存在比$x$ 小的数，用线段树来维护区间最小即可实现

　　接着把两个$x$中间的序列染色， 用MinOK来记录，表示区间内$a_i = 0$，可以染色的最小值。 （线段树区间修改

　　最后把$a_i = 0$ 进行染色（利用线段树点查询

CF现场就想到的算法，然而没有特判存在$q$，pushdown还少打了唔， CF百分百掉分,我要变成pupil了，太惨啦QAQ

代码

 #include<cstring>

 #include<algorithm>

 #include<cstdio>

 #define lson nd<<1

 #define rson nd<<1|1

 #define rd read()

 #define rep(i,a,b) for(int i = (a); i <= (b); ++i)

 #define per(i,a,b) for(int i = (a); i >= (b); --i)

 using namespace std;

 const int N = 3e5, inf = ~0U >> ;

 int MIN[N << ], a[N], L[N], R[N], lazy[N << ], q, n, pos;

 int Mok[N << ];

 int read() {

     int X = , p = ; char c = getchar();

     for(; c > '' || c < ''; c = getchar()) if( c == '-') p = -;

     for(; c >= '' && c <= ''; c = getchar()) X = X *  + c - '';

     return X * p;

 }

 void update(int nd) {

     MIN[nd] = min(MIN[lson], MIN[rson]);

 }

 void pushdown(int nd) {

     if(lazy[nd]) {

         Mok[lson] = lazy[nd];

         Mok[rson] = lazy[nd];

         lazy[lson] = lazy[rson] = lazy[nd];

         lazy[nd] = ;

     }

 }

 void build(int l, int r, int nd) {

     if(l == r) {

         MIN[nd] = a[l] ==  ? inf : a[l];

         return;

     }

     int mid = (l + r) >> ;

     build(l, mid, lson);

     build(mid + , r, rson);

     update(nd);

 }

 int query(int Li, int Ri, int l, int r, int nd) {//查询区间最小

     if(Li <= l && r <= Ri) return MIN[nd];

     int mid = (l + r) >> , re = inf;

     if(Li <= mid) re = min(re, query(Li, Ri, l, mid, lson));

     if(mid < Ri) re = min(re, query(Li, Ri, mid + , r, rson));

     return re;

 }

 int query_pt(int p, int l, int r, int nd) {//查询可以染上的值

     if(l == r) return Mok[nd];

     int mid = (l + r) >> ;

     pushdown(nd);

     if(p <= mid) return query_pt(p, l, mid, lson);

     else return query_pt(p, mid + , r, rson);

 }

 void change(int Li, int Ri, int c, int l, int r, int nd) {

     if(Li <= l && r <= Ri) {

         lazy[nd] = c;

         Mok[nd] = c;

         return;

     }

     int mid = (l + r) >> ;

     pushdown(nd);

     if(Li <= mid) change(Li, Ri, c, l, mid, lson);

     if(mid < Ri) change(Li, Ri, c, mid + , r, rson);

     update(nd);

 }

 int main()

 {

     n = rd; q = rd;

     for(int i = ; i <= n; ++i) {

         a[i] = rd;

         if(!a[i]) pos = i;

         if(!L[a[i]]) L[a[i]] = i;

         R[a[i]] = i;

     }

     if(!L[q] && !pos) return printf("NO\n"), ;//无a[i]=0也无q

     build(, n, );

     for(int i = ; i <= q; ++i) {//必须按颜色从小到大覆盖

         if(!L[i]) continue;

         int minv = query(L[i], R[i], , n, );

         if(minv < i) return printf("NO\n"), ;

         change(L[i], R[i], i, , n, );

     }

     for(int i = ; i <= n; ++i) if(!a[i]) {

         a[i] = query_pt(i, , n, );

         if(i == pos && !L[q]) a[i] = q; // 必须存在q

         else if(!a[i]) a[i] = ;

     }

     printf("YES\n");

     for(int i = ; i <= n; ++i) printf("%d ", a[i]);

     putchar('\n');

 }

CF 1023D Array Restoration - 线段树的相关教程结束。