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

Правка ru1, от 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)$$$.

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru1 Русский 163onmyneck 2022-07-08 11:57:40 544 Первая редакция (опубликовано)