NGUỒN : VNU-OI 2020
Cho một hoán vị (chỉ số bắt đầu từ ) của số tự nhiên đầu tiên. Lúc đầu, . Bạn cần lần lượt thực hiện thao tác, mỗi thao tác có một trong hai dạng sau:
- : Đảo ngược đoạn con liên tiếp từ chỉ số đến chỉ số của ;
- : Dịch đoạn con liên tiếp từ chỉ số đến chỉ số của theo vòng tròn sao cho sau khi thực hiện thao tác bằng trước khi thực hiện thao tác .
Sau mỗi thao tác, hãy tìm số cặp nghịch thế (số cặp chỉ số thỏa mãn và ).
Dữ liệu vào:
- Dòng đầu tiên chứa hai số nguyên ;
- dòng tiếp theo, mỗi dòng là một trong hai dạng thao tác đã được miêu tả ở trên.
Dữ liệu ra:
- Sau mỗi thao tác, hãy in ra trên một dòng riêng biệt số cặp nghịch thế của hiện tại theo modulo .
Ví dụ:
Dữ liệu vào:
2 3
S 1 1 1
R 0 1
R 0 0
Dữ liệu ra:
Dữ liệu vào:
2 3
R 0 1
S 0 1 0
R 1 1
Dữ liệu ra:
Giới hạn:
- số điểm: ;
- số điểm khác: ;
- số điểm còn lại: Không có ràng buộc gì thêm.
