Gợi ý bài CNTSEQ - Số lượng dãy con

Link bài CNTSEQ - Số lượng dãy con

Trước hết các bạn nghiên cứu giải bài NUMMAX - Dãy chứa max (Đây là bài thi THHV lần thứ XV ở Sơn La - 2019)

Quay lại bài CNTSEQ - Số lượng dãy con:

• Gọi là giá trị khác nhau sắp xếp tăng dần của dãy .
• Ta tính là số dãy con của dãy có giá trị lớn nhất của phần tử trong dãy đúng bằng
• Khi đó với mỗi truy vấn , ta tìm hai chỉ số nhỏ nhất và lớn nhất sao cho và , khi đó ta có đáp số cho truy vấn là .