题目

给你一个整数 n，表示一个包含从 1 到 n 按顺序排列的整数数组 nums。此外，给你一个二维数组 conflictingPairs，其中 conflictingPairs[i] = [a, b] 表示 a 和 b 形成一个冲突对。

从 conflictingPairs 中删除 恰好 一个元素。然后，计算数组 nums 中的非空子数组数量，这些子数组都不能同时包含任何剩余冲突对 [a, b] 中的 a 和 b。

返回删除 恰好 一个冲突对后可能得到的 最大 子数组数量。

子数组 是数组中一个连续的 非空 元素序列。

示例 1

输入： n = 4, conflictingPairs = [[2,3],[1,4]]

输出： 9

解释：

• 从 conflictingPairs 中删除 [2, 3]。现在，conflictingPairs = [[1, 4]]。
• 在 nums 中，存在 9 个子数组，其中 [1, 4] 不会一起出现。它们分别是 [1]，[2]，[3]，[4]，[1, 2]，[2, 3]，[3, 4]，[1, 2, 3] 和 [2, 3, 4]。
• 删除 conflictingPairs 中一个元素后，能够得到的最大子数组数量是 9。

示例 2

输入： n = 5, conflictingPairs = [[1,2],[2,5],[3,5]]

输出： 12

解释：

• 从 conflictingPairs 中删除 [1, 2]。现在，conflictingPairs = [[2, 5], [3, 5]]。
• 在 nums 中，存在 12 个子数组，其中 [2, 5] 和 [3, 5] 不会同时出现。
• 删除 conflictingPairs 中一个元素后，能够得到的最大子数组数量是 12。

提示：

• 2 <= n <= 10^5
• 1 <= conflictingPairs.length <= 2 * n
• conflictingPairs[i].length == 2
• 1 <= conflictingPairs[i][j] <= n
• conflictingPairs[i][0] != conflictingPairs[i][1]

思路

大致思路

这道题的核心是“在众多选择中找到最优解”，即移除哪个冲突对能使得最终的有效子数组数量最多。

尝试计算无效子数组并是很困难的，因为不同的子数组可能包含多个冲突对，导致重复计算，如果再考虑排除它们需要用到复杂的容斥原理，并且可预见的要遍历很多次数组。所以我们尝试计算有效子数组。

1. 计算基准与收益：我们将问题分解为两部分：
   • 首先，计算一个基准，即假设不移除任何冲突对时，有多少个有效的子数组。
   • 然后，我们考察当移除某一个冲突对时，相比于基准情况，能增加多少个有效子数组。这个增加的数量就是收益，并且在这里，我们可以不用拘泥于删除全部的数组进行尝试，而是可以凭借规律直接计算那些有可能有收益的情况，可以进行一个巨大的剪枝。
2. 寻找最优策略：我们只需要遍历所有可能产生收益的移除方案，计算出每种方案的收益，然后找出那个最大的收益。

最终答案就是：基准有效数量 + 最大收益。

具体思路

步骤 1：预处理冲突信息

• 目的：将原始的、无序的 conflictingPairs 列表，转换成一种便于快速查询的格式。
• 实现：遍历 conflictingPairs 数组。对于每一个冲突对 {u, v}（u < v），我们都视其为对终点 v 的一个限制，限制强度为 u。由于移除一个冲突对后，我们需要知道次强的限制是什么，因此我们用两个数组 m_first 和 m_second 来记录对于每个终点 v，限制最强（u最大）和次强（u次大）的分别是哪个起始点。这一步将后续的查询复杂度从遍历降到了 O(1)。

步骤 2：计算基准线和筛选候选项

• 目的：在一次遍历中完成三项重要任务：计算limit数组、计算初始有效数量、筛选出值得计算收益的候选项。
• 实现：
  1. 计算limit数组: limit[i] 是解题的关键。它代表“任何以i或更早位置为结尾的子数组，其起始点不能早于limit[i]，否则必为无效”。它通过 limit[i] = max(limit[i-1], m_first[i]) 动态计算，综合了直到当前位置 i 为止的所有冲突限制。
  2. 计算初始有效数量 (result): 在算出 limit[i] 后，以 i 结尾的有效子数组数量就是 i - limit[i]。您在循环中通过 result += i - limit[i]，将所有位置的有效数量累加起来，得到了在包含所有冲突对时的总有效子数组数量，这就是我们的基准。
  3. 筛选vary_num: 移除一个冲突对 {u, v} (即 m_first[v] = u) 能产生收益的充要条件是 u > limit[v-1]。您的代码 if(m_first[i] > limit[i-1]) 正是利用这个条件，将所有可能产生收益的终点 v存入了 vary_num。这极大地减少了下一步需要计算的案例数量。

步骤 3：高效计算最大收益

• 目的：对于每一个筛选出的候选项，计算其能带来的收益，并找出最大值。
• 实现：这是算法最核心的优化部分。
  1. 外层循环 for (int v : vary_num) 只遍历那些我们真正关心的候选项。
  2. 内层循环 for (int j = v; j <= n; ++j) 是一个模拟过程。不尝试完整构建新的 limit_new 数组，而是用一个变量 limit_new_tracker 来模拟 limit_new 值的传播。
  3. 通过 current_gain += (long long)limit[j] - limit_new_at_j;，它累加了每一步 j 上有效子数组的增加量。
  4. 最关键的优化是 if (limit_new_at_j >= limit[j]) { break; }。一旦新的 limit 值“追上”了旧的，就意味着后续不再有收益，可以立即停止模拟，大大提高了效率。

步骤 4：合成最终答案

• 目的：将基准和最大收益相加。
• 实现：result = result + max_gain。

代码实现

class Solution {
public:
    long long maxSubarrays(int n, vector<vector<int>>& conflictingPairs) {

        std::ios_base::sync_with_stdio(false);
        std::cin.tie(NULL);
        
        vector<int> m_first(n + 1, 0); // 对于包含每个元素的冲突对中较小元素的最大值的显示列表
        vector<int> m_second(n + 1, 0); // 对于包含每个元素的冲突对中较小元素的次大值的显示列表
        vector<int> limit(n + 1, 0); // 对于之后的线性扫描中，以i为结尾的子数组其队头的限制列表，在这个数以及之前的数的数组都是无效数组。
        long long result = 0; // 最大有效子数组数量
        vector<int> vary_num; // 记录limit发生变化的数，即我们需要关心的数

        int bigger; int smaller; // 每一组冲突数中较大和较小的那个

        for(int i = 0; i < conflictingPairs.size(); i++) // 将冲突对信息保存在最大值和次大值数组中
        {
            if(conflictingPairs[i][0] >= conflictingPairs[i][1])
            {
                bigger = conflictingPairs[i][0];
                smaller = conflictingPairs[i][1];
            }

            else
            {
                bigger = conflictingPairs[i][1];
                smaller = conflictingPairs[i][0];
            }

            if(smaller > m_first[bigger]) // 较小值是最大值
            {
                m_second[bigger] = m_first[bigger];
                m_first[bigger] = smaller;
            }

            else if(smaller > m_second[bigger]) // 较小值是次大值
            {
                m_second[bigger] = smaller;
            }
        }

        for(int i = 1; i <= n; i++) // 计算limit数组
        {
            limit[i] = limit[i-1];

            if(m_first[i] > limit[i-1]) // 当前这个位置有较大值为这个位置的冲突对，和前一个位置比较。
            {
                limit[i] = m_first[i];
                vary_num.push_back(i); // 记录下一步我们需要关心的点
            }

            result += i - limit[i]; //计算总result
        }

        long long max_gain = 0;

        // vary_num 存储了所有需要计算收益的终点 v (即满足 u > limit[v-1] 的那些 v)
        for (int v : vary_num) 
        {
            
            long long current_gain = 0;
            
            long long limit_new_tracker = limit[v-1]; 

            for (int j = v; j <= n; ++j) 
            {
                // 确定在 j 点，我们应该用哪个 m 值
                long long current_m_val;
                if (j == v) {
                    current_m_val = m_second[v]; // 在移除点 v，使用次大值
                } else {
                    current_m_val = m_first[j];  // 在其他点 j，使用原始的最大值
                }

                // 计算理论上在 j 点的 limit_new 值
                long long limit_new_at_j = max(limit_new_tracker, current_m_val);

                // 如果新的 limit 已经追上或超过了旧的 limit，收益停止增加，可以退出内循环
                if (limit_new_at_j >= limit[j]) {
                    break;
                }

                // 累加本步 j 带来的收益 (有效子数组的增加量)
                current_gain += (long long)limit[j] - limit_new_at_j;

                // 更新追踪器，为下一步 (j+1) 做准备
                limit_new_tracker = limit_new_at_j;
            }

            // 更新最大收益
            if (current_gain > max_gain) {
                max_gain = current_gain;
            }
        }
        
        result = result + max_gain;

        return result;

    }
};

复杂度分析

时间复杂度: O(N^2+P)

1. 预处理 conflictingPairs (计算 m 数组):
   • for(int i = 0; i < conflictingPairs.size(); i++)
   • 这个循环运行的次数等于冲突对的数量，我们称之为 P。
   • 复杂度为: O(P)
2. 计算 limit 数组和 base_result:
   • for(int i = 1; i <= n; i++)
   • 这个循环从 1 运行到 n。
   • 复杂度为: O(N)
3. 计算最大收益 (max_gain):
   • for (int v : vary_num): 这是外层循环。vary_num 的大小最坏情况下可能接近 N。
   • for (int j = v; j <= n; ++j): 这是内层循环。在最坏情况下，break 条件可能很晚才触发，导致这个循环也接近运行 N 次。
   • 因此，这一部分在理论上的最坏情况下，复杂度是 O(N×N)=O(N2)。

空间复杂度: O(N)

• m_first 和 m_second 数组:
  • vector<int> m_first(n + 1, 0);
  • vector<int> m_second(n + 1, 0);
  • 这两个向量的大小都与 n 成正比。
  • 空间为: O(N)
• limit 数组:
  • vector<int> limit(n + 1, 0);
  • 大小与 n 成正比。
  • 空间为: O(N)
• vary_num 数组:
  • vector<int> vary_num;
  • 在最坏情况下，这个向量可能存储接近 n 个元素。
  • 空间为: O(N)