1313 - SỬA CHUỖI

Ta sẽ xây dựng một cây Segment tree với mỗi node là một Stack và chúng ta sẽ lưu (len, type) với len là độ dài của Stack và type là tính chất của ngoặc vuông hoặc tròn tại đáy của Stack vì việc đổi chiều dấu ngoặc là không tốn chi phí. Đặt type = 0 nếu ngoặc tại i là ngoặc tròn, ngược lại type = 1. Ta có thể dễ dàng nhận thấy rằng Stack của mỗi node sẽ có dạng 10101 … hoặc 01010… phụ thuộc vào type và len. Các trường hợp giúp ta kết hợp 2 node a và b bất kì:

• Nếu a.len = 0, kết quả sẽ là b và ngược lại
• Nếu lastA \neq b.type (lastA là đỉnh trên của Stack), kết quả sẽ là (a.len + b.len, a.type).
• Nếu lastA = b.type (lastA là đỉnh trên của Stack), kết quả sẽ là (a.len − b.len, a.type) nếu a.len ≥ b.len, ngược lại là (b.len−a.len, newFirst) (newFirst là đáy của Stack khi kết hợp a và b)

Độ phức tạp: Q \times log(n) cho mỗi test.