Solutions of Subarray

Select solution language

menkh Created at 17 likes

Đối với bài toán này, ta không thể áp dụng binary search một cách đơn thuần được, vì mảng có chứa số âm nên prefix sum sẽ không đơn điệu. Theo yêu cầu đề bài, ta có:

p r e f [j] - p r e f [i - 1] \leq S

$pref[j]-pref[i-1] \le S$

⟺ p r e f [i - 1] \geq p r e f [j] - S

$\iff pref[i-1] \ge pref[j]-S$ Lúc này với mọi chỉ số

i

$i$ thoả mãn, ta sẽ lấy chỉ số

i

$i$ nhỏ nhất thoả mãn đồng thời

p r e f [i - 1]

$pref[i-1]$ phải đủ lớn để thoả

p r e f [i - 1] \geq p r e f [j] - S

$pref[i-1] \ge pref[j]-S$ . Nhận thấy rằng, nếu có hai chỉ số

i_{1} < i_{2}

$i_1 < i_2$ và

p r e f [i_{1}] \geq p r e f [i_{2}]

$pref[i_1] \ge pref[i_2]$ , thì ta sẽ luôn luôn chọn chỉ số

i_{1}

$i_1$ vì

i_{1}

$i_1$ nhỏ hơn, đồng thời vẫn đủ lớn để thoả điều kiện. Đơn giản là vì nếu giá trị cực đại của

p r e f [i_{1}]

$pref[i_1]$ không thoả mãn

p r e f [i_{1}] \geq p r e f [j] - S

$pref[i_1] \ge pref[j]-S$ , thì sẽ không có bất cứ giá trị nào mà bé hơn

p r e f [i_{1}]

$pref[i_1]$ thoả mãn được cả. Từ quan sát trên, gọi

c a n d i d a t e []

$candidate[]$ là danh sách gồm các giá trị

p r e f [i]

$pref[i]$ có thể thoả mãn. Ban đầu,

c a n d i d a t e [0] = 0

$candidate[0]=0$ . Và với mỗi chỉ số

0 < i \leq n

$0 < i \le n$ , ta sẽ đẩy

i

$i$ vào danh sách nếu

p r e f [i]

$pref[i]$ lớn hơn giá trị

p r e f [j]

$pref[j]$ cực đại trong

c a n d i d a t e

$candidate$ . Từ đây

c a n d i d a t e []

$candidate[]$ chỉ gồm các giá trị

p r e f [j]

$pref[j]$ tăng dần. Lúc này ta có thể áp dụng binary search để tìm

p r e f [i - 1]

$pref[i-1]$ nhỏ nhất thoả mãn

p r e f [i - 1] \geq p r e f [j] - S

$pref[i-1] \ge pref[j] - S$ Độ phức tạp:

O (n \log (n))

$O(n\log(n))$