Chuỗi cân bằng đồng thời

Lời giải: Chuỗi cân bằng đồng thời

Hướng tiếp cận

Dùng stack đơn điệu và map prefix-vector để đếm các cặp đoạn đồng thời hợp lệ.

Nhận xét quan trọng

1. Đoạn $[l,r]$ hợp lệ với chuỗi $k$ ↔ tổng tiền tố $\text{pref}[k][r+1]=\text{pref}[k][l]$ và $min(\text{pref}[k][l..r+1])=\text{pref}[k][l]$.
2. Vị trí $l$ "chết" với chuỗi $k$ khi $\text{pref}[k][j]<\text{pref}[k][l]$: duy trì stack đơn điệu per chuỗi để loại bỏ.
3. Map từ vector tiền tố → số vị trí còn sống: đếm các $l$ có cùng prefix vector với $j$.

Thuật toán

Duyệt $j$ từ 0 đến $N$:

1. Pop từ stack của mỗi chuỗi $k$ các vị trí $l$ với $\text{pref}[k][l]>\text{pref}[k][j]$ → đánh dấu chết, xóa khỏi map.
2. ans += map[vec(j)].
3. Thêm $j$ vào map và tất cả stack.

Độ phức tạp

• Thời gian: $O(NK\log N)$
• Bộ nhớ: $O(NK)$