最长上升子序列

最长上升子序列(Longest Increasing Subsequence)

int len[__];

int LIS(int a[],int n)
{
    int lis=0;
    for(int i=1;i<=n;++i)
    {
        int x=lower_bound(len+1,len+lis+1,a[i])-len;
        len[x]=a[i],lis=max(x,lis);
    }
    return lis;
}

最长上升子序列方案数

struct node
{
    int x,p,ans;

    bool operator<(const node &b)const
    {
        if(x!=b.x)return x<b.x;
        return p<b.p;
    }
}dp[__];

int n,a[__],b[__],len[__];

/*
树状数组:
单点修改void add(int x,int val)
查询前缀和int sum(int x)
*/

int main()
{
    sf("%d",&n);
    for(int i=1;i<=n;++i)
        sf("%d",&a[i]),b[i]=a[i];

  //离散化数组a[]
    sort(b+1,b+1+n);
    int m=unique(b+1,b+1+n)-b-1;
    fup(i,1,n)a[i]=lower_bound(b+1,b+1+m,a[i])-b;

  //求最长上升子序列及其每个数的深度
    int lis=0;
    for(int i=1;i<=n;++i)
    {
        int x=lower_bound(len+1,len+lis+1,a[i])-len;
        len[x]=a[i];
        dp[i]={x,i,1};
        lis=max(x,lis);
    }

    sort(dp+1,dp+n+1);
  //x->第i层, y->第i+1层
    int x=1,y=0,ans=0;

  //初始化第一层, 使y指向第二层
    while(++y<=n && dp[y].x==1)
        if(lis==1)++ans;

    for(int i=1;i<lis;++i)
    {
        int z=y;
      //双指针
        for(;y<=n && dp[y].x==i+1;++y)
        {
            for(;x<=n && dp[x].x==i && dp[x].p<dp[y].p;++x)
                T.add(a[dp[x].p],dp[x].ans);
            dp[y].ans=1ll*dp[y].ans*T.sum(a[dp[y].p]-1)%mod;
            if(i+1==lis && (ans+=dp[y].ans)>=mod)
                ans-=mod;
        }
      //清空树状数组
        for(--x;dp[x].x==i;--x)
            T.clear(a[dp[x].p]);
        x=z;
    }
    printf("%d\n",ans);
    return 0;
}