Trong bài này, với mỗi vị trí \(i\) bạn cần tính \(L[i]\) và \(R[i]\) lần lượt là 2 vị trí xa nhất về phía bên trái và bên phải của \(i\) mà mọi số \(a\) trong đoạn từ \(i\) tới vị trí ấy đều $ \leq a[i] $. Ví dụ, \(a[j] \leq a[i]\) với \(L[i] \leq j \leq i\). Có nhiều cách giải quyết vấn đề này : dùng stack, hoặc thậm chí là QHĐ?!

Sau đó bạn duyệt qua tất cả vị trí \(i\) mà \(a[i] = b\), khi ấy đáp án được cộng thêm một lượng \((i-L[i]+1) * (R[i]-i+1)\)

Có một lưu ý nhỏ : Bạn hãy xem test VD sau

n = 5, b = 6

1 6 2 6 3

Bạn dễ tính được L[2] = L[4] = 1, R[2] = R[4] = 5

Như thế theo công thức sẽ có ít nhất một đoạn con bị tính lại 2 lần, đó là đoạn \([1,5]\).

Đó là lí do trong công thức, bạn cần lưu lại vị trí \(j\) gần nhất mà \(a[j] = b\). Lúc này cập nhật L[i] = max(L[i],j+1) thì công thức trên sẽ đúng!