题解：AT_abc360_g [ABC360G] Suitable Edit for LIS

· · 题解

开幕先致敬一下经典：

时隔高达 6 场 abc，LIS 问题它又回来了！

感觉和 E 差不多难吧，虽然我赛时没做。

这种题先求两个东西，就是以 i 为起点的 LIS 长度和以 i 为终点的 LIS 长度，分别记为 L_i 和 R_i。这部分可以用树状数组求出，具体可看我的 SP57 题解。

然后考虑枚举修改第 i 个位置，则第 i 次修改后包含 a_i 的 LIS 最长为：

L_{i+1}+\max_{1\le j<i,a_j+2\le a_{i+1}}\{R_j\}+1

然后对于每个 i 取这个式子最大值就行了。但是要注意的是你还要特判前面或后面不取 LIS 的情况，这一点在求出 L_i,R_i 的时候就可以解决掉。

以及，直接做是 O(n^2) 的，所以还是考虑用树状数组进行优化，就可以通过了。

然而，普通的实现方式需要进行复杂的离散化，且可能需要多判断一些东西，所以我们可以用 unordered_map 充当树状数组，不离散化直接做。然后再分析一下这样做的复杂度：

时间复杂度：如果你把 unordered_map 的复杂度视为常数的话，时间复杂度是 O(n\log a_i)。

空间复杂度：每次最多在哈希表上多产生 O(\log a_i) 的节点，所以空间复杂度也是 O(n\log a_i)。

综上，这种算法可以通过本题。

#include<bits/stdc++.h>
#define N 200005
using namespace std;
const int inf=1e9+7;
unordered_map<int,int>c;
int n,a[N],l[N],r[N],ans;
void add(int x,int k){
    while(x<=inf){
        c[x]=max(c[x],k);x+=x&-x;
    }
}
int ask(int x){
    int ans=0;
    while(x){
        ans=max(ans,c[x]);x-=x&-x;
    }
    return ans;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i){
        r[i]=ask(a[i]-1)+1;
        add(a[i],r[i]);
        ans=max(ans,r[i]+(i!=n));
    }
    c.clear();
    for(int i=n;i>=1;--i){
        l[i]=ask(inf-a[i]-1)+1;
        add(inf-a[i],l[i]);
        ans=max(ans,l[i]+(i!=1));
    }
    c.clear();
    for(int i=1;i<=n;++i){
        int k=ask(a[i+1]);
        ans=max(ans,l[i+1]+k+1);
        add(a[i]+2,r[i]);
    }
    cout<<ans;
    return 0;
}