Hướng giải: Thủy triều

Tiến hành gom toàn bộ truy vấn và sắp xếp các truy vấn theo thứ tự tăng dần mực nước ~x~. Duyệt qua với mỗi truy vấn, sử dụng Hai con trỏ (Two Pointers) tiến hành xử lý các điểm có độ cao theo thứ tự tăng dần và nhỏ hơn hoặc bằng mực nước, đồng thời duy trì một danh sách các đoạn khu vực có thể nhìn thấy được.

Nếu một điểm tại chỉ số ~i~ bị thủy triều bao phủ, xảy ra một trong ~4~ trường hợp:

• Vùng đất đoạn ~[l, r]~ còn tồn tại trước đó (với ~l<i<r~). Lúc này phân tách ra hai đoạn ~[l,i-1]~ và ~[i+1,r]~.
• Vùng đất đoạn ~[i,r]~ còn tồn tại trước đó (với ~i<r~) và điểm tại chỉ số ~i-1~ đã bị thủy triều bao phủ. Lúc này đoạn ~[i,r]~ trở thành đoạn ~[i+1,r]~.
• Vùng đất đoạn ~[l,i]~ còn tồn tại trước đó (với ~l<i~) và điểm tại chỉ số ~i+1~ đã bị thủy triều bao phủ. Lúc này đoạn ~[l,i]~ trở thành đoạn ~[l,i-1]~.
• Vùng đất đoạn ~[i,i]~ còn tồn tại trước đó và hai điểm chỉ số ~i-1~, ~i+1~ đều đã bị thủy triều bao phủ. Lúc này đoạn ~[i,i]~ bị xóa hoàn toàn.

Sau khi xử lý các điểm có độ cao nhỏ hơn hoặc bằng mực nước của truy vấn hiện tại, sử dụng Tìm kiếm nhị phân để tính toán kết quả. Có thể sử dụng cấu trúc Ordered Set để dễ dàng xử lý việc thêm, xóa và tính toán kết quả.

Độ phức tạp: ~O(n.log(n)+q.log(q)+q.log(n))~.