We have nn elements.

The edge of [a,b][a, b] cannot be put into the same group where a,ba, b is in zip(allergic, poisonous). The question is: what is the number of continuous ranges that we can have to make sure all elements in this range are valid? The range cannot be empty; however, a range with only one element is allowed.

Example

If we have n=5n = 5:

• allergic = [1,2]
• poisonous = [3,5]

The valid ranges will be: [1],[1,2],[2],[2,3],[3],[2,3,4],[3,4],[4],[3,4,5],[4,5],[5][1], [1,2], [2], [2,3], [3], [2,3,4], [3,4], [4], [3,4,5], [4,5], [5]

Problem Size

Since nn can be as large as 10510^5, an O(n2)O(n^2) algorithm will result in TLE.

Key Insight

After analyzing the example, it's clear that the left-most bolded number in each range is critical to the final answer. If we have that number, we can use the following approach to solve the problem:

for i in range(1, n+1):
    res += i - left_most_number_in_this_row + 1

Finding the Leftmost Number

First, we collect all the information given node ii: what is the largest number of a node on its left side that it cannot stay together with?

Using the given example, we get the following results:

• i=1i = 1, largest conflicting node = -1
• i=2i = 2, largest conflicting node = -1
• i=3i = 3, largest conflicting node = 1
• i=4i = 4, largest conflicting node = -1
• i=5i = 5, largest conflicting node = 2

The corresponding code for this part:

d = collections.defaultdict(lambda: -1)
for a, b in zip(allergic, poisonous):
    a, b = sorted([a, b])
    d[b] = max(d[b], a)

Adjusting the Leftmost Number

Initially, it seems that using "the largest conflicting node + 1" gives us the leftmost number we need. However, this is incorrect.

For instance, when i=4i = 4, we should get 2, but the simple approach fails. To fix this, we use the following transition: Leftmost number of i=max⁡(Leftmost number of i,Leftmost number of i−1)\text{Leftmost number of } i = \max(\text{Leftmost number of } i, \text{Leftmost number of } i-1)

The corresponding code:

for i in range(1, n+1):
    d[i] = max(d[i], d[i-1])

This ensures that we correctly compute the leftmost number for each index and efficiently count the valid ranges.

---

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.