### cfg0d's blog

By cfg0d, history, 7 weeks ago, translation, Statement: We have an array A. Lets take every index i and find L[i] and R[i] — closest left and right index j such that A[j] >= A[i] respectively. Then I state that if for every i in 0..n-1 we sum min(i — L[i], R[i] — i) it will be O(N log N). Its useful if we fix A[i] as the maximum number of segment and if the length of segments is fixed, we can naively iterate over all such segments.

Proof: Lets look at what we actually do. We iterate over i and look at L[i] and R[i] and count the elements to the closest side. If i — L[i] < R[i] — i, lets add segments (i — 1, i), (i — 2, i), ... , (L[i] + 1, i). Else lets add segments (i, i + 1), (i, i + 2), ... (i, R[i] — 1). In all of these segments let the endpoint that is equal to i be the red color and to the other endpoint to be the black color. Obviously this sum we are trying to prove is the number of segments = number of black points. Lets for every i calculate the maximum number of times that it can be the black end of segment. Let index j be the corresponding red end of such segment. I will prove for j > i, because for j < i its symmetrical. Lets take maximum j > i such that j can be red end of this segment. Then A[j] > A[j — 1] and A[j] > A[j — 2] ... A[j] > A[i]. So now lets take second maximum j such than j can be red end of this segment. Lets call the maximum j j1, second maximum j2. Notice that j2 — i <= j1 — j2. Because otherwise we wouldnt take j2 with i, consequently 2 * j2 <= j1 + i. Consequently the number of such j s is maximum log n.

Usage: The most beautiful usage of this I have recently seen in task https://codeforces.com/problemset/problem/1175/F. I was thinking about hashes, etc. , but there is a solution just fixing the maximum of permutation, let it be A[i], find L[i], R[i] and iterate all segments with length A[i] that include i, but neither L[i] nor R[i]. Notice that it`s even less that described above so we can explicitly get our candidates to be the permutations and their number is <= N log N.

You can also check this task https://codeforces.com/contest/1156/problem/E , the same idea is used there in analysis. Comments (11)
 » Your post is marked as russian so it's not visible on english version
•  » » oh.. ok, i changed it
 » Your proof is really hard to understand.
 » 7 weeks ago, # | ← Rev. 3 →   Also, I have an easier proof:Consider the maximum element in the entire array, let it have index $i$. The answer for index $i$ is $min(i-1,n-i)$, (assuming we pad the array with infinity at both ends). Now recursively solve the problems for all numbers to the left of $i$, and to the right of $i$ separately. These subproblems are independent since $a[i]$ is the maximum in the entire array. So our recurrence for the array looks something like:$T(l,r) = T(l,i-1) + T(i+1,r) + min(i-1, N-i)$, where $N = r - l + 1$.It is well known that this recurrence is $T(1,N) = O(N * log(N))$, like you said!
•  » » » Think about the "small to large" merging trick that you gets you the $O(N * log(N))$ runtime on DSU and tree problems.We have a tree here, but it's a recursion tree! Think about the recursion in reverse, and merging the 2 child subproblems in the recursion together. If we do it "small to large" style, we do $O(min(i-1, N-i))$ work, which is what we have in the recurrence. It's the exact same thing, so it's $O(N * log(N))$ also!