Drop One Feud Pair

Hard

There are n houses in a row, numbered 1 to n. The list feuds describes feuding pairs: [a, b] means the households in houses a and b cannot get along. Call a contiguous span of houses (from one house to another, both ends included) **peaceful** if it does not contain both houses of any pair that is still feuding. You must reconcile **exactly one** pair from the list, removing it. Return the largest possible number of non-empty peaceful spans afterwards.

Example 1

n=5, feuds=[[1, 3], [2, 5]] → 13

There are 15 spans in total. Lift the feud [1, 3], leaving [2, 5]: it rules out only the spans holding both 2 and 5, namely [1..5] and [2..5], so 13 peaceful spans remain. Lifting [2, 5] instead leaves [1, 3], which rules out three spans ([1..3], [1..4], [1..5]), giving 12.

Example 2

n=3, feuds=[[1, 2], [1, 2]] → 4

One of the two identical pairs remains, so the spans [1..2] and [1..3] are ruled out: 4 of the 6 remain.

Constraints

2 ≤ n ≤ 10⁵
1 ≤ len(feuds) ≤ 2 · n
feuds[i] = [a, b], 1 ≤ a, b ≤ n, a ≠ b
The same pair may appear more than once

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Segment Tree Array Enumeration Prefix Sum

Similar problems

Ferry Runs From the Depot Hard Balanced Cuts After One Replacement Hard Flowerbed Beauty on a Budget Hard Quadruples With a Swap in the Middle Hard Level the Jars Medium

Input

n=5, feuds=[[1, 3], [2, 5]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 70 tests on the server, hidden ones included.