AFO

题解 P6993 【[NEERC2014]Improvements】

2020-12-22 22:19:08


经过一些手玩或者打表可以发现,合法当且仅当 $\forall i\in[1,n]$,$p_i$ 是一个后缀最小值或者后缀最大值。

必要性证明可以考虑找到 $p_i=n$ 的位置,则前面必然是 $p_1=1,p_2=2,\cdots,p_{i-1}=i-1,p_i=n$,后面是一个子问题,可以递归证明;充分性证明略。

这个结论等价于 $p^{-1}$ 是一个单峰的排列,因为 $p_n$ 前面比它小的数单增、比它大的数单减。

修改一个数和直接删掉没有区别。于是只要正反求两遍 LIS,然后枚举最高点即可。

// ====================================
//   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;

int n,a[N],f[N],g[N],o[N];

int main() {
    n=read();
    for (int i=1;i<=n;++i) a[read()]=i;
    memset(o,0x3f,sizeof(o));
    for (int i=1,c=0;i<=n;++i) {
        int p=upper_bound(o+1,o+c+1,a[i])-o-1;
        f[i]=p+1,o[f[i]]=min(o[f[i]],a[i]),c=max(c,f[i]);
    }
    memset(o,0x3f,sizeof(o));
    for (int i=n,c=0;i>=1;--i) {
        int p=upper_bound(o+1,o+c+1,a[i])-o-1;
        g[i]=p+1,o[g[i]]=min(o[g[i]],a[i]),c=max(c,g[i]);
    }
    int ans=0;
    for (int i=1;i<=n;++i) ans=max(ans,f[i]+g[i]);
    printf("%d\n",ans-1);
    return 0;
}