Editorial for ANT

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

Tóm tắt đề: cho $n$ ~n~ số nguyên được sắp xếp không giảm, với mỗi truy vấn là $2$ ~2~ số nguyên $L$ ~L~ và $R$ ~R~ hãy đếm số vị trí mà tổng độ chênh lệch là nhỏ nhất (độ chênh lệch của 2 số nguyên $a$ ~a~ và $b$ ~b~ là $|a - b|$ ~|a - b|~).

Chia làm 2 trường hợp:

$R - L + 1$ ~R - L + 1~ là một số lẻ (độ dài của truy vấn là một số lẻ). Đáp án sẽ luôn là $1$ ~1~ (là vị trí $a_{(R-L+2)/2}$ ~a_{(R-L+2)/2}~).
$R - L + 1$ ~R - L + 1~ là một số chẵn (độ dài của truy vấn là số chẵn). Đáp án sẽ là $a_{(R-L+1)/2+1} - a_{(R-L+1)/2}+1$ ~a_{(R-L+1)/2+1} - a_{(R-L+1)/2}+1~.

Editorial for ANT

Comments