CF1144G 题解

__vector__ · 2025-04-09 13:13:43 · 题解

虽然我的做法比较唐，但好像没人用双端队列，就来交一个。

做法

假设现在考虑前 i 个，且第 i 个属于上升序列的。

那么，贪心的想一下，显然是此时下降序列的最后一个数的值越大越好。

设 f_{i} 代表考虑前 i 个数，第 i 个数属于上升序列，此时下降序列的最后一个数的最大值是多少。

转移的话，考虑上升序列中 i 的前一个位置 j，分类讨论 j \lt i-1 和 j = i-1，不存在 j 三种情况。

• 若 j \lt i-1。
  那么只要存在一个合法的这样的 j，那么 f_i \leftarrow a_{i-1}。而一个 j 合法的条件是 f_{j} \gt a_{j+1}，并且 [j+1,i-1] 是严格降序。现在问题是怎么快速判定符合条件的 j 是否存在。注意到 f_j \gt a_{j+1} 这个条件仅和 j 有关，考虑每计算出一个 f_k，若 f_k \gt a_{k+1}，那么将其加入一个双端队列的末尾，若 a_k 小于等于双端队列的末尾对应位置的值，那么就把队尾弹出。这样就形成了一个值递增的单调队列。另外，观察第二个条件，容易发现其对于 j 的限制是单调不降的，所以每次可以从双端队列头部弹出不符合第二个条件要求的位置。由于队列的值递增，此时最优的位置一定是队列第一个位置。
• 若 j=i-1。
  只需要满足 a_{i} \gt a_{i-1} 就行了，转移是 f_{i} \leftarrow f_{i-1}。
• 若 j 不存在。
  此时需要满足 [1,i-1] 是严格递减，f_i \leftarrow a_{i-1}。

一个细节：可以令 a_0 = \infty，代表不存在递减序列时，递减序列最后一个数是无穷大，后面接什么都可以。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
const int maxn=2e5+5;
int n;
int a[maxn];
int des[maxn];
int dp[maxn];
int lst[maxn];
deque<int> okids;
bool added[maxn];
bool ans[maxn];
bool wait[maxn];
void solve(int id_of_test){
    read(n);
    bool alldes=1;
    FOR(i,1,n){
        read(a[i]);
    }
    FOR(i,2,n)alldes&=(a[i]>a[i+1]);
    if(alldes){
        puts("YES");
        FOR(i,1,n)printf("%d ",1);
        pln
        return;
    }
    FOR(i,1,n){
        if(a[i]<a[i-1])des[i]=des[i-1];
        des[i]++;
    }
    a[0]=1e9;
    dp[0]=1e9;
    FOR(i,1,n){

        bool can_be_add=0;
        int lim=i-1-des[i-1];
        while(!okids.empty()&&okids.front()<lim){
            okids.pop_front();
        }
        if(!okids.empty()&&a[okids.front()]<a[i]){
            ckmx(dp[i],a[i-1]);
            lst[i]=okids.front();
            can_be_add=1;
        }
        if(a[i]>a[i-1]&&added[i-1]){
            ckmx(dp[i],dp[i-1]);
            if(dp[i]==dp[i-1])lst[i]=i-1;
            can_be_add=1;
        }
        // 还有一种情况，它是第一个节点
        if(des[i-1]==i-1){
            ckmx(dp[i],a[i-1]);
            if(dp[i]==a[i-1])lst[i]=0;
            can_be_add=1;
        }
        if(a[i+1]<dp[i]&&can_be_add){
            wait[i]=1;
        }
        added[i]=can_be_add;

        if(wait[i-1]){
            while(!okids.empty()&&a[i-1]<=a[okids.back()])okids.pop_back();
            okids.eb(i-1);
        }
       // printf("lst[%d] = %d\n",i,lst[i]);
    }
    FOR(i,1,n)ans[i]=1;
    REP(i,n,n-des[n]){
        if(added[i]&&(i==n||a[i+1]<dp[i])){
            puts("YES");
            int nw=i;
            while(nw>=1){
                ans[nw]=0;
                nw=lst[nw];
            }
            FOR(i,1,n){
                printf("%d ",int(ans[i]));
            }
            pln
            return;
        }
    }
    puts("NO");
}
int main()
{
    int T;
    T=1;
    FOR(_,1,T){
        solve(_);
    }
    return 0;
}