Editorial for Tổng giá trị nhỏ nhất

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: Yunan

Subtask 1: Ta đơn giản duyệt qua từng đoạn và tính giá trị nhỏ nhất của đoạn đó. Độ phức tạp: $O(N^3)$ ~O(N^3)~.

Subtask 2: Với mỗi đoạn, sử dụng cấu trúc dữ liệu truy vấn đoạn (Segment Tree, BIT,...) để tính giá trị nhỏ nhất của đoạn đó. Độ phức tạp: $O(N^2log(N))$ ~O(N^2log(N))~.

Subtask 3: Với mỗi $i$ ~i~ ( $1 \le i \le N$ ~1 \le i \le N~), ta tiến hành tính $count_i$ ~count_i~ là số đoạn $[L,R]$ ~[L,R]~ có giá trị nhỏ nhất là $a_i$ ~a_i~. Đáp án của bài toán là tổng các giá trị $a_i.count_i$ ~a_i.count_i~ với mọi $1 \le i \le N$ ~1 \le i \le N~. Với mỗi chỉ số $i$ ~i~, ta cần tính hai giá trị $l_i$ ~l_i~ và $r_i$ ~r_i~:

$l_i$ ~l_i~ là số lớn nhất thỏa mãn $l_i<i$ ~l_i<i~ và $A_{l_i} < A_i$ ~A_{l_i} < A_i~
$r_i$ ~r_i~ là số nhỏ nhất thỏa mãn $r_i>i$ ~r_i>i~ và $A_{r_i} < A_i$ ~A_{r_i} < A_i~

Khi đó, các đoạn $[L,R]$ ~[L,R]~ có giá trị nhỏ nhất là $A_i$ ~A_i~ sẽ thỏa mãn $l_i+1 \le L \le i$ ~l_i+1 \le L \le i~ và $i \le R \le r_i-1$ ~i \le R \le r_i-1~. Từ đó, $count_i=(i-l_i)\times(r_i-i)$ ~count_i=(i-l_i)\times(r_i-i)~.

Việc tính toán các giá trị $l_i$ ~l_i~ và $r_i$ ~r_i~ có thể thực hiện theo thứ tự tăng dần các giá trị $A_i$ ~A_i~. Ta xây dựng một cấu trúc dữ liệu (Set, Segment Tree,...) để lưu trữ các vị trí $i$ ~i~ của giá trị $A_i$ ~A_i~ (lưu ý rằng $1 \le A_i \le N$ ~1 \le A_i \le N~). Với mỗi $i$ ~i~, sử dụng phương pháp tìm kiếm nhị phân để tìm hai giá trị lân cận của $i$ ~i~ trong cấu trúc dữ liệu, hai giá trị đó chính là $l_i$ ~l_i~ và $r_i$ ~r_i~ cần tính.

Độ phức tạp: $O(NlogN)$ ~O(NlogN)~

Editorial for Tổng giá trị nhỏ nhất

Comments