UVa1471 Defense Lines（LIS变形）

题目链接

1.题目描述：给定一个长度为n的序列，现在可以删除一段任意长度的子序列，使得删除后剩下的序列中有长度最大的连续递增子序列

2.这个题目很新颖，刚开始看裸写了一个LIS，一看样例过了兴致勃勃的交了上去，结果WA了。仔细一看，这里只能删一段序列，并不是任意跳跃式的选择，而且最后的答案是最长的连续递增子序列。如果单纯地求连续递增子序列还好说，现在可有点麻烦

3.顺着刘老师的思路看下去，预处理以i下标开头的最长连续递增子序列长度，以j结尾的最长连续递增子序列长度，那么就是枚举i，快速找一个j<i使得a[j] < a[i]而且g(j)+f(i)尽量大。下面讲了使用set的思路，看了看，好长好麻烦，又要插入删除和二分查找，真的不想写。又看到下一页最下面写着：可以用LIS的nlog(n)算法避开set，也就是第二种方法

4.去网上看了看，果不其然，我是看这篇博客学习的。首先整体思路不变，仍然是使用f(i)记录以i结尾的的最长递增子序列的长度，g(i)记录以i开头的最长递增子序列的长度，和普通的LIS类似，利用一个数组d[i]记录长度为 i 的连续递增序列的最后一个元素的最小值，显然该序列是单调递增的，所以可以通过二分查找直接得到f[j]的值，进而得到一个可行的长度ans, 然后更新数组d即可,更新的方法是如果以a[i]小于数组d中记录的与a[i]长度相同的序列的最后一个元素的值，那么把这个值改为a[i], 即 d[f[i]] = min(a[i], d[f[i]]); 最终ans的最大值即为答案

5.其他的都懂，就是为什么d[i]会保证单调性这里真的头看破都想不通，属实无奈便模拟了第一个样例：
9
5 3 4 9 2 8 6 7 1

6.最后简单证明一下为什么d数组是单调的（初始化均为INF）:
设p,q为两个连续的长度，他们对应数组下标分别为i,j，很明显q=p+1且肯定有a[i]<a[j]。假设当前正在判断p、q，如果之前长度p的d[p]没有被更新，那么显而易见；如果之前有p` =p：
①若之前有d[p`]<a[i]，那么d[p`]不更新，一定有d[p`]<a[j]
②若之前有d[p`]>a[i]，那么d[p`]更新为a[i]，后面一定有d[q]由INF更新为a[j]，那么d[p]<a[j]=d[q]
证毕

#include <iostream>
#include <set>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF 0x7fffffff
const int maxn=2e5+10;

int a[maxn],f[maxn],g[maxn],d[maxn];

int main(){
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++){
            if(a[i]>a[i-1])
                f[i]=f[i-1]+1;
            else f[i]=1;
        }
        g[n]=1;
        for(int i=n-1;i>=1;i--){
            if(a[i]<a[i+1])
                g[i]=g[i+1]+1;
            else g[i]=1;
        }
        for(int i=0;i<=n;i++) d[i]=INF;
        int ans=0;
        for(int i=1;i<=n;i++){
            int len=(lower_bound(d+1,d+1+i,a[i])-(d+1))+g[i];
            ans=max(ans,len);
            d[f[i]]=min(a[i],d[f[i]]);
        }
        printf("%d\n",ans);
    }
    return 0;
}