AtCoder

分析

因为要字典序最小,所以可以贪心,从前往后确定所有位,每位尽量填 $0$。

为了方便,我们把是 $p$ 中的前缀最大值的前缀最大值称作“旧的“,不是 $p$ 中前缀最大值的前缀最大值称作”新的“。

首先有一个结论:如果一个 $s$ 合法,那么 $x,y$ 两个序列中一定有一个序列的前缀最大值全都是旧的。

证明可以这样考虑:如果 $x,y$ 中都有一个新的前缀最大值,那么我们交换这两个数,这样子两个序列中就都少了一个新的。

那么我们不妨假设 $x$ 的前缀最大值全是旧的。

我们假设前 $i-1$ 位已经填完了,现在需要判定第 $i$ 位能否填 $0$。

设 $x$ 已经填的数中的前缀最大值有 $cx$ 个,$y$ 已经填的数中前缀最大值有 $cy$ 个,$p_{i..n}$ 中有 $c$ 个旧前缀最大值,$y$ 后面填的数中会有 $k$ 个旧前缀最大值、$m$ 个新前缀最大值,那么应该要有

$$ cx+c-k=cy+k+m $$

$$ 2k+m=cx+c-cy $$

可以发现右边是常数,我们只要判断左边能否满足即可。

不难发现左边的意思其实是把旧前缀最大值看成 $2$、新前缀最大值看成 $1$,求能否在后面找到一个前缀最大值的和是右边的常数的一个子序列。可以发现,如果能找到一个前缀最大值的和是 $x$ 的子序列,那么一定能找到一个和是 $x-2$ 的,所以我们只要求出奇偶最大值即可。

考虑 DP。设 $dp_{i,0/1}$ 表示以 $i$ 开头、和是偶数/奇数的最大和,转移可以用线段树优化。

上面这个是 $x$ 不放的情况,$y$ 不放的情况类似,自己推一下式子即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;
const int inf=0x3f3f3f40;

int n,a[N],w[N],cnt[N]; char s[N];

#define ls (o<<1)
#define rs (o<<1|1)
struct sgt {
    int maxv[N<<2];
    void pushup(int o) { maxv[o]=max(maxv[ls],maxv[rs]); }
    void modify(int o,int l,int r,int p,int w) {
        if (l==r) { maxv[o]=w; return; }
        int mid=(l+r)>>1;
        if (p<=mid) modify(ls,l,mid,p,w);
        else modify(rs,mid+1,r,p,w);
        pushup(o);
    }
    int query(int o,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return maxv[o];
        int mid=(l+r)>>1,res=-inf;
        if (ql<=mid) res=max(res,query(ls,l,mid,ql,qr));
        if (qr>mid) res=max(res,query(rs,mid+1,r,ql,qr));
        return res;
    }
} odd,even;
#undef ls
#undef rs

bool check(int p,int w) {
    if (w<0) return 0;
    if (w&1) return odd.query(1,1,n,p,n)>=w;
    else return even.query(1,1,n,p,n)>=w;
}

int main() {
    n=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1,mx=0;i<=n;++i) {
        if (a[i]>mx) w[i]=2,mx=a[i];
        else w[i]=1;
    }
    memset(odd.maxv,0xc0,sizeof(odd.maxv));
    for (int i=n;i;--i) {
        int mxo=odd.query(1,1,n,a[i],n),mxe=even.query(1,1,n,a[i],n);
        if (w[i]&1) odd.modify(1,1,n,a[i],mxe+w[i]),even.modify(1,1,n,a[i],mxo+w[i]);
        else odd.modify(1,1,n,a[i],mxo+w[i]),even.modify(1,1,n,a[i],mxe+w[i]);
    }
    for (int i=n;i;--i) cnt[i]=cnt[i+1]+w[i]-1;
    int cx=0,cy=0,mxx=0,mxy=0;
    for (int i=1;i<=n;++i) {
        odd.modify(1,1,n,a[i],-inf),even.modify(1,1,n,a[i],0);
        if (check(mxy,cx+(a[i]>mxx)+cnt[i+1]-cy)
          ||check(max(mxx,a[i]),cy+cnt[i+1]-cx-(a[i]>mxx)))
            s[i]='0',cx+=(a[i]>mxx),mxx=max(mxx,a[i]);
        else s[i]='1',cy+=(a[i]>mxy),mxy=max(mxy,a[i]);
    }
    if (cx!=cy) puts("-1");
    else for (int i=1;i<=n;++i) putchar(s[i]);
    return 0;
}
最后修改:2020 年 09 月 24 日 05 : 18 PM