All problems

Fence Painting

Hard · union find

A fence has n planks, numbered 0 to n - 1. At the start every plank is unpainted, which counts as colour 0.

You are given a list strokes. Each stroke is [left, right, colour]: it paints every plank from left to right, both included, with colour. The strokes are applied in the order given, and a new stroke completely covers whatever paint was on those planks before.

Return a list of length n holding the final colour of every plank, from plank 0 to plank n - 1. Planks that no stroke touches stay 0.

Examples

Example 1

Input: n = 6, strokes = [[0, 3, 1], [2, 5, 2]]

Output: [1, 1, 2, 2, 2, 2]

The second stroke covers planks 2 and 3, which the first stroke had painted with colour 1.

Example 2

Input: n = 4, strokes = [[1, 2, 5], [0, 3, 7], [1, 1, 9]]

Output: [7, 9, 7, 7]

The middle stroke hides the first one completely. The last stroke then repaints only plank 1.

Example 3

Input: n = 5, strokes = [[3, 3, 4]]

Output: [0, 0, 0, 4, 0]

Only plank 3 is painted. The others keep colour 0.

Constraints