Bedao Grand Contest 12 - MEDIAN
Xem dạng PDF
Một lớp học nọ ở thị trấn bedao có ~n~ học sinh, mỗi học sinh có chỉ số tốt bụng là ~a_i~. Lớp học được dẫn dắt bởi lớp trưởng lastPledge. Mặc dù ăn ở khá tốt tuy nhiên lastPledge vẫn không vừa lòng được cô giáo chủ nhiệm. Chính vì vậy, trong ~q~ ngày tới, mỗi ngày cô giáo sẽ giao cho lastPledge một nhiệm vụ. Mỗi nhiệm vụ cô giáo giao sẽ thuộc ~1~ trong ~2~ loại sau:
1 i x: lastPledge cần thay đổi chỉ số tốt bụng của bạn học sinh thứ ~i~ thành ~x~.2 l r: lastPledge cần tìm giá trị trả về của đoạn code sau:play(l, r): k = a[l] i = l + 1 while i < r: k = median(k, a[i], a[i + 1]) i = i + 2 return kvới ~\text{median}(x,y,z)~ là số nằm giữa trong ba số ~x,y,z~.
Đây là một nhiệm vụ khó khăn dành cho lastPledge, vì vậy lastPledge cần sự giúp đỡ của các cao nhân để giải bài toán này. Hãy giúp lastPledge nhé!
Input
Dòng đầu gồm ~2~ số nguyên ~n~ và ~q~ ~(1 \le n,q \le 10^6)~.
Dòng tiếp theo gồm ~n~ số nguyên ~a_1,a_2,\ldots, a_n \ (1 \le a_i \le 10^9)~.
~q~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên thể hiện cho nhiệm vụ loại ~1~ hoặc loại ~2~. Với nhiệm vụ loại ~1~ thì ~1 \le i \le n, 1 \le x \le 10^9~, loại ~2~ thì ~1 \le l \le r \le n~.
Output
- Với mỗi nhiệm vụ loại ~2~, in ra trên mỗi dòng là giá trị trả về của nhiệm vụ đó.
Subtask
~50\%~ số test khác có ~n, q \le 10^5~.
~50\%~ số test còn lại không có ràng buộc gì thêm.
Sample Input 1
6 4
4 6 2 3 1 5
2 1 5
2 1 3
1 1 3
2 1 5
Sample Output 1
3
4
3
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.