Idea about array subsegments.

Правка ru7, от Nutella3001, 2021-10-18 23:25:53

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). It`s 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: Iterating over such i we also have the second end of this segment. Lets for every i calculate the maximum number of times that it can be the second end of such segment. Let index j be the first 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 first 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 first end of this segment. Lets call the maximum j j1, second maximum j2. Notice that j2 — i <= j1 — j2. Because otherwise we wouldn`t 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://mirror.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://mirror.codeforces.com/contest/1156/problem/E , the same idea is used there in analysis.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Nutella3001 2021-10-19 16:25:47 521
en1 Английский Nutella3001 2021-10-19 07:46:58 1777 Initial revision for English translation
ru7 Русский Nutella3001 2021-10-18 23:25:53 125
ru6 Русский Nutella3001 2021-10-18 22:13:46 7
ru5 Русский Nutella3001 2021-10-18 22:10:14 1 Мелкая правка: 'mes that i can be th' -> 'mes that it can be th'
ru4 Русский Nutella3001 2021-10-18 22:08:46 6
ru3 Русский Nutella3001 2021-10-18 22:08:03 33 Мелкая правка: 'gment. Let`s for ever' -> 'gment. Lets for ever'
ru2 Русский Nutella3001 2021-10-18 22:07:43 25 Мелкая правка: 'ray A. Let`s take eve' -> 'ray A. Lets take eve'
ru1 Русский Nutella3001 2021-10-18 22:07:31 1616 Первая редакция (опубликовано)