Editorial for Bedan Contest #05 - C - Xâu đối xứng


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: flo

Cách giải

Hint
  • Nếu xâu s là một xâu đối xứng thì xâu con từ vị trí 2 đến |s|-1 của nó cũng sẽ là xâu đối xứng. Để dễ hình dung thì nếu abba là xâu đối xứng thì bb cũng là xâu đối xứng, zsusz là xâu đối xứng thì sus cũng là xâu đối xứng.
Solution
  • Từ nhận xét trên, một đoạn [l, r] sẽ có một cặp (i, j) (l \le i < j \le r) thỏa mãn s_is_{i+1}...s_j là xâu đối xứng khi tồn tại một vị trí i (l \le i)s_i = s_{i+1} (i < r) (1) hoặc s_i = s_{i+2} (i < r-1) (2).
  • Với nhận xét trên, ta sẽ gọi ab lần lượt là 2 dãy chứa các vị trí i của xâu s thỏa mãn điều kiện (1)(2). Sau đó, ta sẽ sắp xếp 2 dãy này theo thứ tự tăng dần. Với mỗi l r của mỗi truy vấn, ta chỉ việc chặt nhị phân trên 2 dãy này và kiểm tra có phần tử nào thuộc đoạn [l, r] thỏa mãn điều kiện còn lại của điều kiện (1) hoặc (2) hay không.
  • Độ phức tạp của ý tưởng trên là O(n + q \times log_2n).


Comments

There are no comments at the moment.