题目描述

难度分:$1982$

输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

你可以修改$a$中恰好一个数（修改成任意整数）。输出$a$的最长严格递增子序列（$LIS$）的长度。

注：子序列不一定连续。

输入样例$1$

4
3 2 2 4

输出样例$1$

3

输入样例$2$

5
4 5 3 6 7

输出样例$2$

4

算法

一周灵茶$AK$时刻！

前后缀分解+线段树优化DP

这个题自己要写的代码非常短，大部分的代码都是经典问题和数据结构，可以直接复制粘贴模板。比较直观的一个思路就是要枚举这个要操作的元素$a[i]$，$f[x]$是以$a[x]$结尾的最长上升子序列长度，$g[y]$是以$g[y]$开头的最长上升子序列长度。这两个数组可以用$O(nlog_2n)$求$LIS$的方法求出来，这是个经典的算法，可以用同一个模板（用模板求出$f$，再把$a$逆序并求相反数，求出$g$，把$g$反转过来即可，注意求完$g$后还原$a$数组）。

如果$x \lt i \lt y$，只要$a[x]+1 \lt a[y]$，就可以把$a[i]$修改为$[a[x]+2,a[y]-1]$里面的某个数，从而把以$a[x]$结尾的最长上升子序列和以$a[y]$开头的最长上升子序列接起来。构建一个线段树，索引是$a[i]$（注意$a$数组的值域比较大，需要对其进行离散化），索引上对应的值是$f[i]$，初始情况下线段树上所有索引位置上都是$0$。

然后枚举这$y$，这时候需要为$i$腾一个位置出来，这个位置至少是$i=y-1$，所以$x$的位置应该满足$x \leq y-2$，当遍历到$y$的时候就要把$f[y-2]$插入到线段树的$a[y-2]$位置。接下来求线段树在值域$[1,a[y]-1)$上的最大值就可以了，这就是我们需要的最大$f[x]$，维护$1+f[x]+g[y]$的最大值。

注意$i=1$、$i=n$这两个边界情况，分别没有$x$和$y$，需要特判一下。

复杂度分析

时间复杂度

预处理出$f$和$g$的时间复杂度是$O(nlog_2n)$的；遍历$y$求解是$O(n)$的，但对于每个$y$，需要对线段树进行单点修改和区间查询操作，时间复杂度为$O(log_2n)$。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

线段树的空间复杂度为$O(n)$；对$a$数组中的元素进行离散化空间消耗为$O(n)$；$f$和$g$两个数组的时间复杂度为$O(n)$；对线段树进行递归的时候递归深度是$O(log_2n)$规模的，空间复杂度为$O(log_2n)$。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int n, a[N], f[N], g[N];

class SegmentTree {
public:
    struct Info {
        int l, r, v;
        Info() {}
        Info(int left, int right, int val): l(left), r(right), v(val) {}
    } seg[N<<2];

    explicit SegmentTree() {}

    void build(int u, int l, int r) {
        if(l == r) {
            seg[u] = Info(l, r, 0);
        }else {
            int mid = l + r >> 1;
            build(u<<1, l, mid);
            build(u<<1|1, mid + 1, r);
            pushup(u);
        }
    }

    void modify(int pos, int val) {
        modify(1, pos, val);
    }

    Info query(int l, int r) {
        if(l > r) return Info(0, 0, 0);
        return query(1, l, r);
    }

private:
    void modify(int u, int pos, int val) {
        if(seg[u].l == pos && seg[u].r == pos) {
            seg[u] = Info(pos, pos, val);
        }else {
            int mid = seg[u].l + seg[u].r >> 1;
            if(pos <= mid) {
                modify(u<<1, pos, val);
            }else {
                modify(u<<1|1, pos, val);
            }
            pushup(u);
        }
    }

    Info query(int u, int l, int r) {
        if(l <= seg[u].l && seg[u].r <= r) {
            return seg[u];
        }
        int mid = seg[u].l + seg[u].r >> 1;
        if(r <= mid) {
            return query(u<<1, l, r);
        }else if(mid < l) {
            return query(u<<1|1, l, r);
        }else {
            return merge(query(u<<1, l, r), query(u<<1|1, l, r));
        }
    }

    void pushup(int u) {
        seg[u] = merge(seg[u<<1], seg[u<<1|1]);
    }

    Info merge(const Info& lchild, const Info& rchild) {
        Info info;
        info.l = lchild.l;
        info.r = rchild.r;
        info.v = max(lchild.v, rchild.v);
        return info;
    }
};

void get(int dp[]) {
    vector<int> ends;
    for(int i = 1; i <= n; i++) {
        if(ends.empty()) {
            ends.push_back(a[i]);
            dp[i] = 1;
        }else{
            if(a[i] > ends.back()){
                ends.push_back(a[i]);
                dp[i] = ends.size();
            }else {
                int p = lower_bound(ends.begin(), ends.end(), a[i]) - ends.begin();
                dp[i] = p + 1;
                ends[p] = a[i];
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    vector<int> vals;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        vals.push_back(a[i]);
    }
    // 离散化a的元素值
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    // 预处理出f和g
    get(f);
    reverse(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) {
        a[i] *= -1;
    }
    get(g);
    reverse(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) {
        a[i] *= -1;
    }
    reverse(g + 1, g + n + 1);
    int sz = vals.size();
    int ans = f[n];      // 初始化答案为原始的LIS长度
    SegmentTree seg;
    seg.build(1, 1, sz);
    for(int i = 3; i <= n; i++) {
        int index = lower_bound(vals.begin(), vals.end(), a[i - 2]) - vals.begin() + 1;
        seg.modify(index, f[i - 2]);
        index = lower_bound(vals.begin(), vals.end(), a[i] - 1) - vals.begin() + 1;
        ans = max(ans, 1 + g[i] + seg.query(1, index - 1).v);    // 小于a[i]-1的f最大值
    }
    if(f[n - 1] == f[n]) {
        ans = max(ans, f[n] + 1);
    }
    if(g[1] == g[2]) {
        ans = max(ans, f[n] + 1);
    }
    printf("%d\n", ans);
    return 0;
}