Факт про ближайшие большие слева и справа

Revision ru1, by 163onmyneck, 2022-07-08 11:57:40

Привет, codeforces!

У меня вопрос:

Если у нас есть массив $$$a$$$ длины $$$n$$$ (не обязательно перестановка), $$$L_i$$$ — индекс ближайшего слева от $$$i$$$ элемента массива, который $$$≥$$$ чем $$$a_i$$$, а $$$R_i$$$ — индекс ближайшего $$$>$$$ (строго большего!) справа, то какая хорошая оценка сверху на: $$$\sum\limits_{i=1}^n min(i - L_i, R_i - i)$$$?

Я знаю, что если $$$R_i$$$ — больше или равный, то это $$$O(n log n)$$$.

Буду рад услышать ваши ответы!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian 163onmyneck 2022-07-08 11:57:40 544 Первая редакция (опубликовано)