Editorial for Bedao Grand Contest 12 - MEDIAN


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Nhận xét: Với mỗi đoạn ~[l,r]~, giả sử ~a[l+1], a[l+2],\ldots,a[r]~ cố định thì tồn tại hai số ~x~ và ~y~ sao cho nếu ~a[l]\lt x~ thì kết quả hàm ~play~ là ~x~, nếu ~a[l]\gt y~ thì kết quả là ~y~, còn không kết quả là ~a[l]~.

Từ nhận xét này ta có hướng giải của bài toán là sử dụng IT. Ta sẽ xây 2 IT khác nhau tương ứng với tính chẵn lẻ của ~l~ (hàm ~play~ sẽ duyệt qua từng cặp chỉ số liên tiếp). Mỗi nút trên cây sẽ lưu hai số ~x,y~ theo nhận xét ứng với đoạn tương ứng trên mảng.

Với hai nút con có ~x_1,y_1~ và ~x_2,y_2~ thì nút cha sẽ có giá trị ~x=\min(\max(x_1,x_2),y_2)~ và ~y=\max(\min(y_1,y_2),x_2)~. Việc cập nhật IT và lấy kết quả xin nhường cho bạn đọc.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.