题解 | [NC95]数组中的最长连续子序列

$\rm [NC95]数组中的最长连续子序列$

$\quad$

$\rm Solution$

$\quad$ 认真读题可以发现，本题中数之间的相对位置并不重要，于是我们可以想到将它们按权值排序。同时，由于相同的数字并不能同时出现在答案中，所以可将排序后的数列去重。

$\quad$ 考虑枚举排序后的数列，假设当前枚举到 $a_i$ ，记 $now$ 表示以 $a_i$ 为结尾的最长连续子序列。可以发现，如果 $a_i=a_{i-1}+1$ ，那么该序列的长度可以 $+1$ ，否则只能重新开始计算。

$\quad$ 算法流程如图：

$\quad$ 这样做，我们只需要经过 “排序”，“去重” 和 “枚举计算” 三个步骤就可以将答案计算出来，复杂度瓶颈在排序，可以使用快速排序算法，时间复杂度 $\Theta(n\log n).$

$\quad$ 前两步还有另外一种方法，即使用 $C\rm ++$ 自带的 $\rm STL$ 函数 $set$ ，它可以自动完成排序和去重功能，用法如下：

S.insert(x) ：将 $x$ 插入一个 $\rm set$ 类型的数据结构 $S$ 中。
set <int> :: iterator it = S.begin() ：获取 $S$ 头端的迭代器，这个迭代器可以执行 it++ 和 it-- 语句。
set <int> :: iterator it = S.end() : 同上，获取 $S$ 尾端的迭代器。
*it : 如果这个迭代器 $it$ 属于一个 $\rm set$ 类型，那么 *it 可以访问这个迭代器指向的值。

$\quad\rm set$ 类型内存储的值是有序且去重的，所以只要将 $a$ 中的数一个个加入其中，就可以自动完成前两步操作。

$\quad\rm set$ 类型的单次操作时间复杂度是 $\Theta(\log n)$ ，所以总时间复杂度也是 $\Theta(n\log n).$

$\rm Solution-Plus$

$\quad$ 我们发现这个题太水了，于是考虑加强它 :

维护一个数组中的最长连续权值，支持插入和删除。

$\quad$ 我们重新观察这题要求的东西 —— 最长连续权值，如果将所有数都以权值为下标， $1$ 为值插入线段树中，那么答案就是最长的一段连续的 $1.$

$\quad$ 在线段树中修改是很容易的，我们考虑如何维护答案。

$\quad$ 对每个线段树中的点（线段）记录：

包含左端点的最长连续 $1$ 的长度，记它为 $Lmax$ 。
包含右端点的最长连续 $1$ 的长度，记它为 $Rmax$ 。
整段区间中最长连续 $1$ 的长度，记它为 $Max$ 。

$\quad$ 更新 $Max$ 时，只需要取其左儿子的 $Rmax$ 和其右儿子的 $Lmax$ 相加即可。

$\quad$ 更新 $Lmax$ 的时候，如果它左儿子的 $Max$ 等于左儿子维护区间的长度，那么意味着左儿子维护的区间是连续权值区间，将 $Lmax$ 更新为左儿子的 $Max$ 与右儿子的 $Lmax$ 之和即可。

$\quad$ 更新 $Rmax$ 可以使用一样的方法。

$\quad$ 在任意时刻，答案即为线段树根节点的 $Max.$

$\quad$ 我们发现单次修改的时间复杂度为 $\Theta(\log n)$ ，一开始的预处理可以看作将所有数重新插入一遍。记加入和删除操作的次数为 $m$ ，那么总时间复杂度为 $\Theta((n+m)\log n).$

$\rm Code$

class Solution {
public :
    int MLS (vector<int> &a) {
        int n = a.size(), cnt = 0, ans = 0;

        sort(a.begin(), a.end());
        // 将数据排序

        for (int i = 0; i < n; i++)
            if (a[i] != a[cnt]) a[++cnt] = a[i];
        // 将数据去重

        for (int i = 1, now = 1; i <= cnt; i++) {
            if (a[i] == a[i - 1] + 1) now++;
            // 如果 a[i] 相对于 a[i - 1] 是连续的，那么以 a[i] 为结尾的答案 +1
            else now = 1;
            // 否则只能以 a[i] 为开头重新统计
            ans = max(ans, now);
            // 一边统计一边更新答案
        }

        return ans;
    }
};