线段树优化 dp。

#include<bits/stdc++.h>
using namespace std;
const size_t MAXN=5e5+5;
int n,b[MAXN],f[MAXN][2],a[MAXN],ans=0,maxn=0;
// f[i][0]: 以i结尾长度偶数，f[i][1]: 以i结尾长度奇数
struct Tree{
    int l,r,v;
}t[MAXN];
inline void pushup(int x){
    t[x].v=max(t[x<<1].v,t[x<<1|1].v);
}
void bt(int x,int l,int r){
    t[x].l=l,t[x].r=r;t[x].v=0;
    if(l==r)
        return ;
    int mid=(l+r)>>1;
    bt(x<<1,l,mid);
    bt(x<<1|1,mid+1,r);
}
void upd(int x,int k,int w){
    if(t[x].l==t[x].r)
        return (void)(t[x].v=w);
    int mid=(t[x].l+t[x].r)>>1;
    if(k<=mid)
        upd(x<<1,k,w);
    else
        upd(x<<1|1,k,w);
    pushup(x);
}
int query(int x,int l,int r){
    if(l>r)
        return 0;
    if(l<=t[x].l&&t[x].r<=r)
        return t[x].v;
    // cerr<<"now query: "<<x<<" "<<t[x].l<<" "<<t[x].r<<" "<<l<<" "<<r<<'\n';
    int mid=(t[x].l+t[x].r)>>1,ans=0;
    if(l<=mid)
        ans=max(ans,query(x<<1,l,r));
    if(mid<r)
        ans=max(ans,query(x<<1|1,l,r));
    return ans;
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i),maxn=max(maxn,a[i]);
    bt(1,1,maxn);
    // cerr<<"end bt\n";
    for(int i=1;i<=n;i++){
        f[i][1]=max(query(1,1,a[i]-1),query(1,a[i]+1,maxn))+1;
        // cerr<<"end query\n";
        upd(1,a[i],f[i][0]=(b[a[i]]!=0)*(b[a[i]]+1));
        // cerr<<"end upd\n";
        b[a[i]]=max(b[a[i]],f[i][1]);
        ans=max(ans,f[i][0]);
    }
    printf("%d",ans);
    return 0;
}