Привет. Есть такая задачка: Дано какой-то комбинация p[]

от 1 до n чисел. надо найти позиция самого большого число в интервале [ p[1] . . p[n] ], допусим это будет k. потом тоже самое повторить рекурсивно для [p[1].. p[k-1] ] and [ p[k + 1] ..p[n]]] , пока не дойдем пустой интервал. Тут для каждого найденного k , умножаю размер левый и правый интервал: (k-1) * (n - k -1). и рекурсивно для каждого [1..k-1] and [k+1..n] интервалом тоже умножаю. потом их переумножаю... результат будет умножение всех таких длин интервалом.

Например, n = 4
p [] = { 1, 4, 3, 2} : max=4, k = 2: left interval [1] , right [3, 2] : mul_1 = | [1] | * | [3, 2] | = 1 * 2 = 2

потом, рекурсив:
[ 1 ] : k = 1: left interval = [], right interval = [] - для пустые интервалом mul=1. то есть, mul_2 = 1 * 1 = 1

[3,2]: max = 3, k = 1: left = [] , right = [2], mul_3 = 1 * 1 = 1

result = mul_1 * mul_2 * mul_3 = 2 * 1 * 1 = 2
——————————————————
Сейчас для нахождение максимум в интервале [a..b) - использую segment tree.

Но можно ли все это операция выполнить за линейное время? Изначальное комбинация статическая , не меняется никогда.

Я правильно понимаю, что ты один раз для массива строишь дерево и делаешь 1 запрос - вычисление этой функции на всём массиве? Получается что-то типа O(n + log(n) * n) в худшем случае?

для p [ 1.. n] = { p[1], p[2] ..., p[n] } — сначала создаю rev[ ] массив , для каждого значение какое позиция стоит. for i = 1.. n : rev[ p [i ] ] = i . потом, mx [ 1 .. 2*n ] : строю сегмент трее: mx[n .. n+n] = p[1..n], mx[i] = max(mx[i*2], mx[i*2+1]) for i = n-1 .. 1 потом вызываю рекурсивную функцию с аргументами, 1, n + 1: int rec(int a, int b) { if (a >= b) return 1; //for empty interval 1 int max_index = find_max_index(a,b); int left_mul = (max_index == a) ? 1 : max_index - a; int right_mul = (max_index + 1 == b ? 1 : b - max_index - 1); return left_mul * right_mul * rec(a, max_index) * rec(max_index + 1 , b); }