3480. Maximize Subarrays After Removing One Conflicting Pair Hard

1/**
2 * [3480] Maximize Subarrays After Removing One Conflicting Pair
3 *
4 * You are given an integer n which represents an array nums containing the numbers from 1 to n in order. Additionally, you are given a 2D array conflictingPairs, where conflictingPairs[i] = [a, b] indicates that a and b form a conflicting pair.
5 * Remove exactly one element from conflictingPairs. Afterward, count the number of <span data-keyword="subarray-nonempty">non-empty subarrays</span> of nums which do not contain both a and b for any remaining conflicting pair [a, b].
6 * Return the maximum number of subarrays possible after removing exactly one conflicting pair.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <span class="example-io">n = 4, conflictingPairs = [[2,3],[1,4]]</span>
11 * Output: <span class="example-io">9</span>
12 * Explanation:
13 * 
14 * 	Remove [2, 3] from conflictingPairs. Now, conflictingPairs = [[1, 4]].
15 * 	There are 9 subarrays in nums where [1, 4] do not appear together. They are [1], [2], [3], [4], [1, 2], [2, 3], [3, 4], [1, 2, 3] and [2, 3, 4].
16 * 	The maximum number of subarrays we can achieve after removing one element from conflictingPairs is 9.
17 * </div>
18 * <strong class="example">Example 2:
19 * <div class="example-block">
20 * Input: <span class="example-io">n = 5, conflictingPairs = [[1,2],[2,5],[3,5]]</span>
21 * Output: <span class="example-io">12</span>
22 * Explanation:
23 * 
24 * 	Remove [1, 2] from conflictingPairs. Now, conflictingPairs = [[2, 5], [3, 5]].
25 * 	There are 12 subarrays in nums where [2, 5] and [3, 5] do not appear together.
26 * 	The maximum number of subarrays we can achieve after removing one element from conflictingPairs is 12.
27 * </div>
28 *  
29 * Constraints:
30 * 
31 * 	2 <= n <= 10^5
32 * 	1 <= conflictingPairs.length <= 2 * n
33 * 	conflictingPairs[i].length == 2
34 * 	1 <= conflictingPairs[i][j] <= n
35 * 	conflictingPairs[i][0] != conflictingPairs[i][1]
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/maximize-subarrays-after-removing-one-conflicting-pair/
41// discuss: https://leetcode.com/problems/maximize-subarrays-after-removing-one-conflicting-pair/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn max_subarrays(n: i32, conflicting_pairs: Vec<Vec<i32>>) -> i64 {
47        
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_3480() {
59    }
60}
61