1632
правки
Изменения
м
<code>
</code>
rollbackEdits.php mass rollback
=== Псевдокод ===
'''function''' precalc(A: '''int[N]'''):
K = <tex>\lceil</tex>N / block_size<tex>\rceil</tex> <font color=green> // количество блоков </font>
<font color=green>// предподсчитаем позиции минимумов в каждом блоке</font>
cur_block = 0 j = 0 -1
'''for''' i = 0 '''to''' K - 1
B[i] = -1
'''for''' i = 0 '''to''' K - 1
ind = (1 << (j - 1)) + i
'''if''' ind <tex>\geq</tex> ≥ K
ST[i][j] = ST[i][j - 1]
'''else if''' A[ST[i][j - 1]] > A[ST[ind][j - 1]]
j = 0
i = 0
'''while''' i < N or j < Kblock_size '''if''' j <tex>\geqslant</tex> ≥ block_size
j = 0
cur_block++
'''if''' j > 0 '''and''' (i <tex>\geqslant</tex> ≥ N '''or''' A[i - 1] < A[i])
type[cur_block] += (1 << (j - 1))
i++
'''for''' r = l + 1 '''to''' block_size - 1
block_min[t][l][r] = block_min[t][l][r - 1]
'''if''' i * block_size + r <tex>\leqslant </tex> ≤ N '''and''' A[i * block_size + block_min[t][l][r]] > A[i * block_size + r]
block_min[t][l][r] = r
'''return''' A[block_RMQ(bl, l % block_size, r % block_size)]
'''if''' bl + 1 < br <font color=green>// найдем минимум на блоках между крайними, если таковые есть</font>
power = log(br - bl + - 1)
ansb = min(A[ST[bl + 1][power]], A[ST[br - (1 << power)][power]])
ansl = A[block_RMQ(bl, l % block_size, block_size - 1)] <font color=green>// найдем минимум на отрезке от l до конца блока, содержащего l</font>
ansr = A[block_RMQ(blbr, 0, r % block_size)] <font color=green>// найдем минимум от начала блока, содержащего r, до r </font>
'''return''' min(ansb, min(ansl, ansr))
=== Результат ===
