Độ khó: Khá (3/4 điểm)

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Trường THPT Hoa Sen tổ chức phong trào thi đua giữa ~N~ lớp, đánh số từ ~1~ đến ~N~. Ban đầu lớp thứ ~i~ có ~a_i~ điểm thi đua. Trong suốt học kì có ~Q~ sự kiện xảy ra lần lượt, mỗi sự kiện thuộc một trong ba loại:

• 1 i x: lớp ~i~ được cộng thêm ~x~ điểm.
• 2 i: thầy Sơn (tổng phụ trách) hỏi thứ hạng hiện tại của lớp ~i~, được tính bằng ~1~ cộng với số lớp có điểm lớn hơn hẳn điểm của lớp ~i~ (các lớp bằng điểm nhau có cùng thứ hạng).
• 3 k: thầy Sơn hỏi điểm của lớp đứng ở vị trí thứ ~k~ khi xếp tất cả các lớp theo điểm giảm dần (các lớp bằng điểm vẫn chiếm các vị trí khác nhau).

Hãy trả lời tất cả các câu hỏi.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(1 \le N, Q \le 2 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(0 \le a_i \le 10^9)~.
• ~Q~ dòng tiếp theo, mỗi dòng mô tả một sự kiện theo định dạng ở trên, với ~1 \le i \le N~, ~1 \le x \le 10^9~, ~1 \le k \le N~.

Kết quả

Với mỗi sự kiện loại ~2~ hoặc ~3~, in ra câu trả lời trên một dòng.

Giới hạn (Subtask)

• Subtask 1 (~30\%~ số điểm): ~N, Q \le 5000~.
• Subtask 2 (~30\%~ số điểm): điểm của mọi lớp ở mọi thời điểm đều không vượt quá ~10^6~.
• Subtask 3 (~40\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 3 giây.

Sample Input 1

4 8
5 8 5 2
2 1
3 1
1 4 6
2 4
3 2
1 1 4
2 3
3 3

Sample Output 1

2
8
1
8
4
8

Giải thích

Ban đầu điểm là ~(5, 8, 5, 2)~: lớp ~1~ có một lớp hơn điểm nên đứng hạng ~2~; lớp cao điểm nhất có ~8~ điểm. Sau khi lớp ~4~ được cộng ~6~ điểm, điểm là ~(5, 8, 5, 8)~: lớp ~4~ đứng hạng ~1~ (bằng điểm lớp ~2~), và khi xếp giảm dần ~8, 8, 5, 5~ thì vị trí thứ ~2~ có ~8~ điểm. Sau khi lớp ~1~ được cộng ~4~ điểm, điểm là ~(9, 8, 5, 8)~: lớp ~3~ có ba lớp hơn điểm nên đứng hạng ~4~; dãy giảm dần là ~9, 8, 8, 5~ nên vị trí thứ ~3~ có ~8~ điểm.

Nguồn: Đề tự luyện HSG Tin học lớp 12 (đề tự soạn).