### Hướng giải và nhận xét
**Quy ước:** phạm vi truy vấn của dãy sẽ có dạng $[l_q, r_q]$
**Ta có một nhận xét như sau:** Với mỗi truy vấn $[l_q, r_q]$
- Giá trị $\min$ của các dãy $[l_q, i]$ là $a[l_q]$ với những $i$ bé hơn vị trí $r$ của phần tử bên phải gần nhất $ > a[l_q]$
- Và các giá trị khác vẫn **giữ nguyên** trước đó
Nên ta dùng [Monotic Stack](https://wiki.vnoi.info/algo/data-structures/Stack) để với mỗi $i$ ta tìm được phần tử bên phải nhỏ nhất lớn hơn $a[i]$
- Duyệt $l$ giảm dần
- Dùng [Segment Tree](https://wiki.vnoi.info/algo/data-structures/segment-tree-extend) để lưu giá trị min của $[l, i]$ với $l$ đang xét
- Cập nhật toàn bộ giá trị trong khoảng từ $l$ đến $r - 1$ với $r$ được mô tả ở trên
- Trả lời toàn bộ truy vấn có đầu mút trái ($l_q$) bằng $l$ đang xét bằng cách tính tổng từ $l_q$ và $r_q$
Và để trả lời toàn bộ truy vấn theo kiểu trên thì ta dùng kĩ thuật [Offline Query](https://wiki.vnoi.info/algo/data-structures/segment-tree-extend) để xử lý
minhpnk2
Created at
0 likes