Đảo các đoạn con · canuc80k6506

Cho chuỗi chữ hoa. Mỗi truy vấn đảo ngược đoạn ký tự $[a, b]$ . In chuỗi sau tất cả truy vấn.

Mỗi cặp $a$ $b$ đảo thứ tự các ký tự ở vị trí $a, \dots, b$ của xâu hiện tại. Các vị trí được đánh số từ $1$ và hai đầu đoạn đều được tính.

Dòng đầu chứa $n$ $m$ . Dòng thứ hai chứa xâu ban đầu dài $n$ . Mỗi dòng trong số $m$ dòng tiếp theo chứa $a$ $b$ .

Subtask small: $50$ điểm, gồm $10$ test nhỏ.
Subtask full: $50$ điểm, gồm $10$ test không có giới hạn bổ sung ngoài phần Constraints.
Mỗi test có giá trị $5$ điểm.

Test 1

Input

6 3
ABCDEF
2 5
1 3
4 6

Output

DEAFBC

Giải thích: Đảo vị trí $2, \dots, 5$ được AEDCBF, sau đó đảo $1, \dots, 3$ được DEACBF. Đảo tiếp $4, \dots, 6$ tạo xâu cuối DEAFBC.

Ý tưởng: Tách cây thành L, M=[a,b], R. Gọi applyRev(M): đổi chỗ hai con của gốc M và bật cờ rev. Khi đi xuống một nút, push truyền cờ cho hai con. Sau đó ghép lại L+M+R. Duyệt cuối cũng gọi push, nên thứ tự xuất là thứ tự logic sau mọi đảo.
Chứng minh đúng: Đảo thứ tự một dãy được biểu diễn bởi cây con T tương đương đổi vai trò trái/phải ở mọi nút của T. Cờ rev thực hiện phép đó lười: tại gốc đổi hai con, rồi ghi rằng hai cây con cũng cần đảo. push bảo đảm trước khi đọc cấu trúc con, phép đảo chưa thực hiện được truyền xuống. Vì mỗi thao tác cô lập đúng M và chỉ tác động M, dãy ngoài đoạn không đổi; M trở thành reverse(M), đúng yêu cầu.
Độ phức tạp: Kỳ vọng O(log n) mỗi truy vấn, O(n) bộ nhớ.