9.9训练小结

题意：

给定一个序列(长度<=1e5), 要求从其中任选一段长度为L的子段并删除， 最后问你剩余序列的LIS(严格递增)为多少？

总结：

想到了枚举切割子段的起始点，进而也想到了预处理出以每一个元素为终点的LIS长度(前缀预处理)和以每一个元素为起点的LIS的长度(后缀预处理)，进而也想到了从后往前枚举起始断点并维护一棵持久性权值线段树(持久性指在一次遍历过程中维护一颗线段树，每一个新的状态都可以依托现在的状态去构建(例如：D-Query))， 枚举前一段的终点，在线段树中查后一段中大于这个点中的最大LIS，然而总是wa，最后发现还是没注意一些细节。
（1）后缀预处理以每一个元素为起点的LIS的长度时，buf[]数组的初值应该设为-INF而不是0，因为初始序列可能有负值
（2）只考虑了以前段中的某元素为终点选一段，然后再在后半段中找拼接的，但是忽略了LIS只出现在前半段或后半段的情况， 即以后在解决其他问题时一定要留意有什么可能的特殊情况。
（3）L=0时不是直接取pre[n]做为答案，而是以max{pre[1],pre[2],pre[3],..,pre[n]}作为答案，即以后在解决dp问题时，一定注意"状态的定义"与"最优值"的关联(诸如：dp[i]是前1~i段中的最值，还是以i为结尾的段的最值)。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define mid ((l+r)>>1)
const int maxn=1e5+10;
const int INF=0x3f3f3f3f; 
int a[maxn],ind[maxn],m;
int n,L,pre[maxn],suf[maxn],buf[maxn];
int maxx[maxn<<2];
void init(){
    int i,j;
    for(i=1;i<=n;i++) buf[i]=INF;
    for(i=1;i<=n;i++){
        j=lower_bound(buf+1,buf+n+1,a[i])-buf;
        buf[j]=a[i]; pre[i]=j;
    }
    for(i=1;i<=n;i++) buf[i]=-INF;
    for(i=n;i>=1;i--){
        j=upper_bound(buf+i,buf+n+1,a[i])-buf-1;
        buf[j]=a[i]; suf[i]=n+1-j;
    }
}
void build(int l,int r,int u){
    maxx[u]=0;
    if(l==r) return ;
    build(l,mid,u<<1); build(mid+1,r,u<<1|1); 
}
void update(int p,int v,int l,int r,int u){
    if(l==r) {maxx[u]=max(maxx[u],v); return ;}
    p<=mid ? update(p,v,l,mid,u<<1) : update(p,v,mid+1,r,u<<1|1);
    maxx[u]=max(maxx[u<<1],maxx[u<<1|1]);
}
int query(int pl,int pr,int l,int r,int u){
    if(pl>pr) return 0; //注意此处还要判断查询区间不合法的情形 !!! 
    if(pl<=l&&r<=pr) return maxx[u];
    int res=0;
    if(pl<=mid) res=query(pl,pr,l,mid,u<<1);
    if(pr>mid) res=max(res,query(pl,pr,mid+1,r,u<<1|1));
    return res;
}
int main(){
    int t,i,j,k,id,ans,cnt=0;
    cin>>t;
    for(;t;t--){
        scanf("%d%d",&n,&L); m=0;
        for(i=1;i<=n;i++){
            scanf("%d",&a[i]);
            ind[++m]=a[i];
        }sort(ind+1,ind+m+1); m=unique(ind+1,ind+m+1)-ind-1;
        init(); ans=0;
        if(L==0) ans=*max_element(pre+1,pre+n+1);
        else {
            build(1,m,1);
            for(i=n-L;i>=1;i--){
                id=lower_bound(ind+1,ind+m+1,a[i])-ind;
                ans=max(ans,query(id+1,m,1,m,1)+pre[i]);
                if(i+L<=n) {
                    id=lower_bound(ind+1,ind+m+1,a[i+L])-ind;
                    update(id,suf[i+L],1,m,1);
                }
            }
            for(i=L+1;i<=n;i++) ans=max(ans,suf[i]);
        }
        printf("Case #%d: %d\n",++cnt,ans);
    } 
    return 0;
}