Изменения

На новой последовательности <tex>B_i</tex> построим [[Решение RMQ с помощью разреженной таблицы|разреженную таблицу]]. Теперь для ответа на запрос <tex>RMQ</tex><tex>[il:jr]</tex>, если <tex>il</tex> и <tex>jr</tex> находятся в разных блоках, нам необходимо вычислить следующее:# минимум на отрезке от <tex>il</tex> до конца блока, содержащего <tex>il</tex>;# минимум по всем блокам, находящимся между блоками, содержащими <tex>il</tex> и <tex>jr</tex>;# минимум от начала блока, содержащего <tex>jr</tex>, до <tex>jr</tex>.

cur_block = 1 0 j = 0 '''for''' i = 1 0 '''to''' K - 1

'''for''' i = 1 0 '''to''' N - 1 '''if''' j <tex>\ge</tex> block_size j = 10 curcur_block++ '''if''' B[curcur_block] = -1 '''or''' A[B[curcur_block]] > A[i] B[curcur_block] = i <font color=green>// построим Sparse table на массиве B</font> '''for''' i = 0 '''to''' K - 1 ST[i][0] = B[i] '''for''' j = 1 '''to''' log(N) '''for''' i = 0 '''to''' K - 1 ind = (1 << (j - 1)) + i '''if''' ind <tex>\ge</tex> K ST[i][j] = ST[i][j - 1] '''else if''' A[ST[i][j - 1]] > A[ST[ind][j - 1]] ST[i][j] = ST[ind][j - 1] '''else''' ST[i][j] = ST[i][j - 1] <font color=green>// Посчитаем хеш для каждого блока {{---}} он будет являться типом блока</font> cur_block = 0 j = 0 '''for''' i = 0 '''to''' K - 1 hash[i] = 0 '''for''' i= 0 '''to''' N - 1 '''if''' j <tex>\ge<tex> block_size j = 0 cur_block++ '''if''' j > 0 '''and''' (i <tex>\ge</tex> n '''or''' A[i - 1] < A[i]) hash[cur_block] += (1 << (j - 1)) <font color=green>// Осталось только для каждого блока предподсчитать позиции минимумов на всех подотрезках</font> '''for''' i = 0 '''to''' K - 1 '''for''' l = 0 '''to''' block_size - 1 '''for''' r = 0 '''to''' block_size - 1 block_min[i][l][r] = -1 '''for''' i = 0 '''to''' K - 1 type = hash[i] '''if''' block_min[type][0][0] = -1 <font color=green>// если там записано, что-то отличное от -1, то значит, мы уже посчитали ответ для такого типа отрезков</font> '''for''' l = 0 '''to''' block_size - 1 block_min[type][l][l] = l '''for''' r = l + 1 '''to''' block_size - 1 block_min[type][l][r] = block_min[type][l][r - 1] '''if''' i * block_size + r <tex>\le</tex> N '''and''' A[i * block_size + block_min[type][l][r]] > A[i * block_size + r] block_min[type][l][r] = r  '''int''' block_RMQ(block_number : '''int''', l : '''int''', r : '''int''') '''return''' block_min[hash[block_number]][l][r] + block_number * block_size  '''int''' RMQ(l : '''int''', r : '''int''') bl = l / block_size br = r / block_size '''if''' bl = br <font color=green>// если оба индекса внутри одного блока</font> '''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(bl, 0, r % block_size)] <font color=green>// найдем минимум от начала блока, содержащего r, до r </font> '''return''' min(ansb, min(ansl, ansr))