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.