题解：P8776 [蓝桥杯 2022 省 A] 最长不下降子序列

本蒟蒻接触 OI 半年以来的第一篇题解，不会树状数组，只好使用朴素的拼接计算的方式了。

这是对变量名以及缩写的解释：

• ：最长不降子序列。（Longest Not Decrease Sequence）
• ：最长不升子序列。（Longest Not Increase Sequence）
• ：原数组。
• ：保存某一长度的最长…… 子序列的末尾值。
• ：保存以某数为结尾的最长…… 子序列的长度。
• ：保存以某数为开头的最长…… 子序列的长度。

Part_1 dp 正确性证明

显然肯定要去赋值。对于原数组的 进行子段赋值的操作，我们只需要考虑在哪两个 节点之间，并不用考虑它们之间的精确位置，所以可以特殊性地认为所选子段均在靠右的节点的正左边，为拼接操作做准备。

（如下图，两种方案对答案并没有实质性的影响，# 表示被选。表示没有 [] 表示被赋值。）

..#.....#...[....]...#...#
..#.....#......[....]#...#

Part_2 dp 策略的分析

提取出一般的状态是这样的：

....#..[....]#.... （具体个数不定）
        i    j

我们确定子段的最后一个下标为 ，子段后的 节点为 。

那么当前情况的 长度应该是 且最大值不超过 的 长度 子段长度 。

处理完之后 指针向前遍历，窗口向前滑，我们要把 纳入左半边 的考虑。

也就是说 query 的是 位置，而 insert 的是 位置的内容。

Part_3 dp 策略的实现

在最初找 的 的时候用的方法是二分，找的是 上不超过 的位置，我们找最大值不超过 的在 上的 长度用的是相同的方法（默认会 的 等）。

该怎么找？老的套路很方便的可以找到 ，所以我们的方式是倒过来看，从结尾开始，截止到 的 即可。

更多详细内容在代码的注释部分。

#include<bits/stdc++.h>

using namespace std;

int n, k;
vector<int> a, fend, flen, fbegin;
// 本人非常喜欢用 STL :)

int binSearchNotIncrease(int len, int val) {
    int l = 0, r = len - 1, mid, ans = -1;
    // 如果返回值为 -1 则证明没有找到 fend[mid] < val
    while (l <= r) {
        mid = (l + r) >> 1;
        if (fend[mid] < val) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    return ans;
    // 经典二分 fend[r]<val fend[l]>=val
    // ans = mid => ans更新为目前找到的小于并且最接近val的位置
}
int binSearchNotDecrease(int len, int val) {
    int l = 0, r = len - 1, mid, ans = -1;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (fend[mid] > val) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    return ans;
}
// 同上 请自行类比理解
void in() {
    scanf("%d%d", &n, &k), a.resize(n + 1);
    fend.resize(n + 1), flen.resize(n + 1), fbegin.resize(n + 1);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    return;
}
// 本人喜欢用 vector<> 各位 int[] 大佬见谅
void calculateLNIS() {
    int len = 0;
    for (int i = n - 1; i >= 0; --i) {
        int find_ = binSearchNotIncrease(len, a[i]);
        if (find_ == -1)
            fend[len++] = a[i], fbegin[i] = len;
        // 没有找到 => a[i]小于等于最后一个 => len++, 以 i 为开始的长度为len
        else
            fend[find_] = a[i], fbegin[i] = find_ + 1;
        // 由于下标从 0 开始，所以为 find_ + 1
        // 找到了 => 更新 fend[find_] 为 a[i], 原理与 LIS替换 相同，看不懂自行补课
    }
    return;
}
void solve() {
    calculateLNIS();
    // 首先计算逆序的 LNIS 准备好
    int len = 0, ans = 0;
    for (int i = 0, j = k, find_; j < n; ++i, ++j) {
        find_ = binSearchNotDecrease(len, a[j]);
        // 先找 i 左边(len维护) 比 <=a[j] 的 LNDS 长度，这个是查询的 j
        ans = max(ans, (find_ == -1 ? len : find_) + fbegin[j] + k);
        // find_ == -1 => 没有找到比 a[j] 更大的 => len 维护的左半边 LNDS长度 即为左半边长度
        // 当前结果 ans 与 左半边+右半边+子段长度 求 max
        find_ = binSearchNotDecrease(len, a[i]);
        if (find_ == -1)
            fend[len++] = a[i];
        else
            fend[find_] = a[i];
        // 经典 insert(i)
    }
    ans = max(ans, len + k);
    // 由于是从 LNDS 节点开始考虑的，所以还要注意一种结尾的情况
    cout << ans;
    return;
}

int main() {
    in();
    solve();
    return 0;
}