You are given n chemicals labeled from 1 to n. Some pairs of chemicals are dangerous and cannot appear together in the same contiguous interval.
The lists poisonous and allergic describe forbidden pairs. For every index i, chemicals poisonous.get(i) and allergic.get(i) cannot coexist.
Count how many contiguous intervals [L, R] are valid such that the interval does not contain both chemicals from any forbidden pair.
A contiguous interval [L, R] contains all chemicals with labels from L to R, inclusive. For example, the interval [2, 5] contains chemicals 2, 3, 4, and 5.
Method Signature
long countValidIntervals(int n, List<Integer> poisonous, List<Integer> allergic)
Parameters
n: the number of chemicals labeled from 1 to n.poisonous: the first chemical of each forbidden pair.allergic: the second chemical of each forbidden pair.poisonous.size() == allergic.size().
Returns
- Return the number of valid contiguous intervals as a
long.
Constraints
1 ≤ n ≤ 200,0001 ≤ poisonous.size() ≤ 200,000poisonous.size() == allergic.size()1 ≤ poisonous.get(i) ≤ n1 ≤ allergic.get(i) ≤ npoisonous.get(i) != allergic.get(i)- If the same forbidden pair appears more than once, it has the same effect as appearing once.
Examples
Example 1
countValidIntervals(n = 4, poisonous = List.of(1), allergic = List.of(3))
Output: 8
Explanation: There are 10 total intervals. The invalid intervals are [1, 3] and [1, 4] because both contain chemicals 1 and 3. Therefore, 8 intervals are valid.
Example 2
countValidIntervals(n = 5, poisonous = List.of(1, 2), allergic = List.of(4, 5))
Output: 12
Explanation: There are 15 total intervals. The invalid intervals are [1, 4], [1, 5], and [2, 5]. Therefore, 12 intervals are valid.
Example 3
countValidIntervals(n = 6, poisonous = List.of(1, 3, 4), allergic = List.of(2, 5, 6))
Output: 11
Explanation: There are 21 total intervals. The forbidden pairs are (1, 2), (3, 5), and (4, 6). An interval is invalid if it contains both chemicals from at least one forbidden pair.
The valid intervals are: [1], [2], [2, 3], [2, 4], [3], [3, 4], [4], [4, 5], [5], [5, 6], and [6].
Therefore, 11 intervals are valid.