📖 Bài giảng & lời giải: đây là Bài tập 2 trong bài giảng Bài 31: Fenwick, Segment Tree trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 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ạm khí tượng ghi lại nhiệt độ của $n$ ngày liên tiếp, ngày $i$ có nhiệt độ $a_i$. Có $q$ thao tác theo thứ tự, mỗi thao tác thuộc một trong hai loại:

• 1 i v: sửa nhiệt độ của ngày $i$ thành $v$;
• 2 l r: tìm nhiệt độ thấp nhất trong các ngày $l, l + 1, \ldots, r$, và ngày sớm nhất (chỉ số nhỏ nhất) trong đoạn đó đạt nhiệt độ thấp nhất ấy.

Dữ liệu vào

• Dòng 1: hai số nguyên $n, q$ ($1 \le n, q \le 2 \cdot 10^5$).
• Dòng 2: $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($|a_i| \le 10^9$).
• $q$ dòng tiếp theo, mỗi dòng là một thao tác dạng 1 i v ($1 \le i \le n$, $|v| \le 10^9$) hoặc 2 l r ($1 \le l \le r \le n$).

Dữ liệu bảo đảm có ít nhất một thao tác loại 2.

Kết quả

Với mỗi thao tác loại 2, theo đúng thứ tự, in trên một dòng hai số nguyên: nhiệt độ thấp nhất và ngày sớm nhất đạt nhiệt độ đó, cách nhau một dấu cách.

Sample Input

6 3
4 2 7 2 9 1
2 1 5
1 2 5
2 1 5

Sample Output

2 2
2 4