Editorial for Giá trị hàm số

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 các chỉ số $j$ ~j~ để tính các giá trị hàm $F(i)$ ~F(i)~ tương ứng. Độ phức tạp: $O(N^2)$ ~O(N^2)~.

Subtask 2: Ta viết lại biểu thức $F(i)= \displaystyle \min_{j \neq i}\{(P_i-P_j)+(i-j)\} = \min_{j \neq i}\{(P_i+i)-(P_j+j)\}$ . Từ đó, để tính $F(i)$ ~F(i)~, ta cần tìm $j$ ~j~ sao cho $j \neq i$ ~j \neq i~ và $P_j+j$ ~P_j+j~ đạt giá trị lớn nhất. Có thể giải quyết trong $O(N.log(N))$ ~O(N.log(N))~ bằng cách sắp xếp mảng hoặc $O(N)$ ~O(N)~ bằng cách lưu hai giá trị $\max$ ~\max~.

Subtask 3: Xét trường hợp $P_i>P_j$ ~P_i>P_j~ và $i>j$ ~i>j~, khi đó $F(i)= \displaystyle \min_{j < i}\{(P_i+i)-(P_j+j)\}$ .

Ta xây dựng mảng $A$ ~A~, ban đầu $A_i=-\infty$ ~A_i=-\infty~ với mọi $1 \le i \le N$ ~1 \le i \le N~.

Tiến hành duyệt qua các chỉ số $i$ ~i~ theo thứ tự tăng dần giá trị $P_i$ ~P_i~. Với mỗi $i$ ~i~: $F(i)= \displaystyle \min(F(i), \; P_i+i - \max_{j<i}\{A_j\})$ , đồng thời cập nhật giá trị $A_i=P_i+i$ ~A_i=P_i+i~.

Việc tìm giá trị $\displaystyle \max_{j<i}\{A_j\}$ ~ \displaystyle \max_{j<i}\{A_j\}~ và cập nhật $A_i$ ~A_i~ có thể thực hiện bằng cấu trúc Segment Tree.

Ta xử lý tương tự đối với ba trường hợp $(P_i>P_j,i<j)$ ~(P_i>P_j,i<j)~, $(P_i<P_j,i>j)$ ~(P_i<P_j,i>j)~ và $(P_i<P_j,i<j)$ ~(P_i<P_j,i<j)~.

Độ phức tạp: $O(N.log(N))$ ~O(N.log(N))~

Editorial for Giá trị hàm số

Comments