Tutorial — Harmonious Lineup

Xét một vị trí kết thúc $r$, nếu một đoạn $[a, r]$ chứa hai nghệ sĩ mâu thuẫn thì mọi đoạn dài hơn $[a', r]$ với $a' \le a$ cũng đều chứa cặp mâu thuẫn đó. Vì vậy, các điểm bắt đầu $a$ tạo thành đoạn hòa hợp kết thúc tại $r$ luôn lập thành một khoảng liên tiếp.

Với mỗi nghệ sĩ $r$, hãy tìm vị trí nghệ sĩ $u < r$ lớn nhất có mâu thuẫn trực tiếp với $r$. Để đoạn kết thúc tại $r$ không chứa bất kỳ mâu thuẫn nào xảy ra từ trước, điểm bắt đầu $a$ phải lớn hơn giá trị lớn nhất trong số các vị trí mâu thuẫn đã xuất hiện từ $1$ đến $r$.

Duy trì giá trị biên trái hợp lệ $bound$ tăng dần khi tịnh tiến $r$ từ $1$ đến $n$ bằng kỹ thuật hai con trỏ hoặc mảng tiền tố cực đại. Tại mỗi bước, cập nhật $bound = \max(bound, last[r])$ và cộng thêm $r - bound$ vào kết quả trong thời gian $O(1)$.