「NNEZ Monthly Round 6」LIS

20分

首先考虑$A_i>0$的情况

显然有dp方程：

$$f_i=max_{1\le j<i}\{f_j+1\}(A_j<A_i)$$

边界条件$f[i]=1$

时间复杂度$O(n^2)$，期望得分20分

50分

50分(100分)的数据要求我们在$O(n\log n)$的时间复杂度内解决这个问题

定义序列$D_i$表示对于所有满足$f_k=i$的$k$中，$A_k$最小是多少

$$D_i=min_{f_k=i}\{A_k\}$$

显然序列$D$是单调递增的（想一想，为什么）

我们来考虑如何维护这个序列$D$

假设当前序列$D$的长度为$len$，当前扫描到的元素为$A_i，$分两种情况：

1. 如果$A_i>D_{len}$，那么令$D_{len+1}=A_i$，同时令$len=len+1$，意义为将$A_i$接到以$D_{len}$为结尾的上升子序列后面
2. 如果$A_i\le D_{len}$，那么在序列$D$中二分找到第一个$p$满足$D_p\ge A_i$，令$D_p=A_i$，意义为把以$D_p$为结尾的上升子序列的末尾元素（即$D_p$）换成$A_i$

tips:
lowerbound(D+1,D+len+1,x)-D
可以得到$D$数组中第一个大于等于$x$的位置是第几个

我们来思考一下第二种情况的意义，对于一个上升子序列，我们自然希望在它后面能接更多的元素，那么这个子序列的末尾元素当然是越小越好

扫描完整个序列$A$后，LIS的长度即为序列$D$的长度$len$

时间复杂度$O(n\log n)$，至此期望得分50分

100分

考虑$A_i$可能会等于0的情况

首先，对于一个末尾为$X$的上升子序列，如果我们既可以在它后面接一个$0$，也可以接一个$A_i$(即$A_i>X$)，那么显然接$0$一定不会使答案更劣

所以一个包含$A_i$中所有$0$的上升子序列，一定不会比最长上升子序列短

那么我们可以先把所有的$0$塞进答案子序列里，然后再塞非零的元素

对于剩下的非零元素，我们先考虑其中两个元素$A_i,A_j(i<j)$，设它们之间$0$的个数为$k$

由于我们必须要保证上升子序列中的元素严格递增，并且要保证已经塞进上升子序列中的$0$能够指派一个值，所以如果$A_i$和$A_j$能够被同时塞进答案子序列里，必须要满足：

$$A_i+k<A_j$$

我们定义一个函数$g(i)$表示位置$i$前面$0$的个数，定义$B_i=A_i-g(i)$

那么我们可以塞进答案子序列里的非零元素个数即为序列$B$的LIS长度

证明:
对于任意$i,j$满足$i<j$

$$B_i<B_j\\ \Leftrightarrow A_i-g(i)<A_j-g(j)\\ \Leftrightarrow A_i+[g(j)-g(i)]<A_j\\ \Leftrightarrow A_i+k<A_j$$

最终的答案是序列$B$的LIS长度加上序列$A$中$0$的个数

二分求LIS，期望得分100分

需要注意的是，由于我们已经提前考虑了$0$，所以在计算序列$B$的LIS长度时，需要跳过$A_i=0$的位置

Code

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn=100005;

int n;
int a[maxn];
int d[maxn],len;

int main()
{
    scanf("%d",&n);
    int zero=0;
    d[0]=-0x7f7f7f7f; 
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        if(a[i]==0)
            ++zero;
        else
        {
            a[i]-=zero;
            if(a[i]>d[len])
                d[++len]=a[i];
            else
            {
                int p=lower_bound(d+1,d+len+1,a[i])-d;
                d[p]=a[i];
            }
        }
    }
    printf("%d",len+zero);
}

---

谢罪

之前月赛讲题的时候，条理不甚清晰，错漏诸多，所以特地重新写了一篇自认为相对更加详细严谨的题解

非常抱歉，我什么都会做的（土下座）