Hướng dẫn giải của Chuỗi cân bằng đồng thời

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

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

Đoạn $[l, r]$ hợp lệ với chuỗi $k$ ↔ tổng tiền tố $pref [k] [r + 1] = pref [k] [l]$ và $min (pref [k] [l . . r + 1]) = pref [k] [l]$ .
Vị trí $l$ "chết" với chuỗi $k$ khi $pref [k] [j] < pref [k] [l]$ : duy trì stack đơn điệu per chuỗi để loại bỏ.
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$ :

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

Độ phức tạp

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

Bình luận

Không có bình luận tại thời điểm này.