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

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

考虑枚举排序后的数列，假设当前枚举到 ，记 表示以 为结尾的最长连续子序列。可以发现，如果 ，那么该序列的长度可以 ，否则只能重新开始计算。

算法流程如图 ：

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

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

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

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

类型的单次操作时间复杂度是 ，所以总时间复杂度也是

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

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

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

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

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

• 包含左端点的最长连续 的长度，记它为 。
• 包含右端点的最长连续 的长度，记它为 。
• 整段区间中最长连续 的长度，记它为 。

更新 时，只需要取其左儿子的 和其右儿子的 相加即可。

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

更新 可以使用一样的方法。

在任意时刻，答案即为线段树根节点的

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

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;
    }
};