[DHBB25 - DX14 - 11] Bài 2: STRSORT
Xem dạng PDF
Gửi bài giải
Điểm:
60,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Bạn được giao nhiệm vụ xử lý một chuỗi ký tự bí mật ~S~ trên một tấm bia cổ. Chuỗi ~S~ có độ dài ~N~ và chỉ chứa các chữ cái in thường từ 'a' đến 'z'. Để giải mã thông điệp trên tấm bia, bạn cần thực hiện ~Q~ thao tác sắp xếp trên các đoạn của chuỗi.
Mỗi thao tác được mô tả bởi ba số ~i, j, k~:
- ~i~ và ~j~ xác định một đoạn liên tiếp của chuỗi, từ vị trí ~i~ đến vị trí ~j~.
- ~k~ xác định cách sắp xếp:
- Nếu ~k = 1~: Sắp xếp các ký tự trong đoạn từ ~i~ đến ~j~ theo thứ tự tăng dần (từ 'a' đến 'z').
- Nếu ~k = 0~: Sắp xếp các ký tự trong đoạn từ ~i~ đến ~j~ theo thứ tự giảm dần (từ 'z' đến 'a').
- Sau khi sắp xếp, các ký tự trong đoạn từ ~i~ đến ~j~ sẽ được thay thế bởi dãy ký tự đã sắp xếp.
Yêu cầu: Hãy thực hiện tất cả ~Q~ thao tác và in ra chuỗi ~S~ cuối cùng sau khi hoàn thành các thao tác.
Input
- Dòng 1: Chứa hai số nguyên ~N~ và ~Q~ (~1 \le N \le 2 \times 10^5~, ~1 \le Q \le 50,000~), lần lượt là độ dài chuỗi và số thao tác.
- Dòng 2: Chứa chuỗi ~S~ gồm ~N~ ký tự, chỉ chứa các chữ cái in thường từ 'a' đến 'z'.
- ~Q~ dòng tiếp theo: Mỗi dòng chứa 3 số nguyên ~i, j, k~ (~1 \le i \le j \le N~, ~k \in \{0, 1\}~), mô tả một thao tác.
Output
- Ghi ra một dòng duy nhất chứa chuỗi ~S~ sau khi thực hiện tất cả ~Q~ thao tác.
Sample Input 1
5 2
abcde
1 3 1
3 5 0
Sample Output 1
abedc
Bình luận
bài này điên thật _ làm xong nỗ não :)) khó vãi cả đạn :)) hihihaha mong anh em tìm ra hướng nào dễ hơn dc ko :))