Дан массив а[1], a[2], ..., a[N]. ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ).
Запрос определяется по паре чисел x, y:
Запрос(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }
Даётся M запросов.
Решения за O(N*M) - TLE, нужно что-то побыстрей.
Заранее спасибо.
Запрос определяется по паре чисел x, y:
Запрос(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }
Даётся M запросов.
Решения за O(N*M) - TLE, нужно что-то побыстрей.
Заранее спасибо.
Upd: Проблема решена. Всем спасибо!
(отправилось раньше времени, пытался написать код)
В общем тебе нужно дерево интервалов. Для каждого интервала хранишь лучшую сумму на всем интервале, лучшую сумму, примыкающую к левой границе, и лучшую, примыкающую к правой. И еще просто сумму всех элементов на интервале. И дальше не сложные переходы.
Определим через l, r, t и s лучшую сумму, примыкающую к левой границе, лучшую сумму, примыкающую к правой границе, просто лучшую сумму, и сумму всего интервала.
Переходы:
l[cur] = max( l[left], s[left] + l[right] );
r[cur] = max( r[right], s[right] + r[left] );
t[cur] = max( t[left], t[right], r[left] + l[right] );
s[cur] = s[left] + s[right]
Для листьев
l[cur] = r[cur] = t[cur] = max( 0, a[cur] );
s[cur] = a[cur];
Ну и все вроде.