2906.
Можете ли Вы ответить на эти вопросы - 1
Задана
последовательность целых чисел a1,
a2, ..., an (|ai| ≤ 15007, 1 ≤ n ≤ 50000). Запрос имеет вид:
Query(x, y)
= MAX {ai + ai+1 + ... + aj, x ≤ i ≤ j ≤ y}
Вам необходимо
вывести ответы на заданные m запросов.
Вход. Первая строка содержит значение n. Во второй строке заданы n
целых чисел последовательности. Третья строка содержит количество запросов m. Далее следует m строк, причем i-ая
строка содержит два числа xi
и yi.
Выход. Вывести ответы на m
запросов, по одному ответу в строке.
|
Пример
входа |
Пример
выхода |
|
3 -1 2 3 1 1 2 |
2 |
РЕШЕНИЕ
структуры данных – дерево отрезков
Анализ алгоритма
Для решения
задачи следует реализовать нетривиальное обобщение дерева отрезков. В каждой
его вершине будем хранить четыре величины: сумму summa на этом отрезке, максимальную сумму prefix среди всех префиксов этого отрезка, максимальную сумму suffix среди всех суффиксов, а также
максимальную сумму max подотрезка на
нём. То есть для каждого отрезка ответ будет предпосчитан не только для него,
но и для отрезков, упирающихся в его левую и правую границы.
Пусть отрезок [a..b]
соответствует вершине дерева. Пусть левый его сын содержит информацию по
отрезку [a..m], а правый – по [m+1..b]. Тогда значения величин в корне
пересчитываются через значения величин в сыновьях следующим образом:
prefix[a..b] = max(prefix[a..m],
summa[a..m]
+ prefix[m+1..b])
suffix[a..b] = max(suffix[m+1..b],
suffix[a..m]
+ summa[m+1..b])
max[a..b] = max(max[a..m],
max[m+1..b],
suffix[a..m]
+ prefix[m+1..b])
summa[a..b] = summa[a..m]
+ summa[m+1..b]
Например, исходя
из приведенных равенств, максимальная сумма на отрезке может равняться одному
из следующих значений:
·
максимуму на отрезке левого сына (лучший подотрезок в
текущей вершине целиком помещается в отрезок левого сына);
·
максимуму на отрезке правого сына (лучший подотрезок в
текущей вершине целиком помещается в отрезок правого сына);
·
сумме максимального суффикса в левом сыне и максимального
префикса в правом сыне (лучший подотрезок лежит своим началом в левом сыне, а
концом в правом)
Пример. Пусть некоторая вершина дерева
соответствует отрезку [0..5]:
Тогда дополнительные величины, хранящиеся в
ней, имеют следующие значения:
Пусть указанная
вершина имеет левого [0..2] и правого [3..5] сына, дополнительные значения в
которых имеют значения:
При объединении
отрезков [0..2] и [3..5] дополнительные значения пересчитываются следующим
образом:
prefix[0..5] = max(prefix[0..2],
summa[0..2]
+ prefix[3..5])
= max (2, 0 + 3) = 3
suffix[0..5] = max(suffix[3..5],
suffix[0..2]
+ summa[3..5])
= max (1, 2 – 3) = 1
max[0..5] = max(max[0..2],
max[3..5],
suffix[0..2]
+ prefix[3..5])
= max (4, 3, 2 2 + 3) = 5
summa[0..5] = summa[0..2]
+ summa[3..5]
= 0 – 3 = -3
Реализация алгоритма
Дерево отрезков храним в виде массива SegTree структур Node
длины MAX, где MAX – максимальное количество элементов, которое может храниться
в отрезке.
#define MAX 50010
struct Node
{
int summa, prefix, suffix, max;
} SegTree[4*MAX];
Функция Merge
объединяет соседние отрезки, соответствующие вершинам Left и Right. По
информации в сыновьях пересчитываются данные в отцовской вершине Res, после
чего она возвращается в качестве результата функции Merge.
Node Merge(Node Left, Node Right)
{
Node Res;
Res.prefix = max(Left.prefix,Left.summa + Right.prefix);
Res.suffix = max(Right.suffix,Right.summa + Left.suffix);
Res.summa = Left.summa + Right.summa;
Res.max = max(max(Left.max,Right.max),Left.suffix + Right.prefix);
return Res;
}
На вход
процедуре build построения дерева отрезков передается массив a, номер текущей
вершины дерева v и границы отрезка LeftPos и RightPos, соответствующие вершине v.
void build (int *a, int v, int LeftPos, int RightPos)
{
if (LeftPos == RightPos)
SegTree[v].max = SegTree[v].prefix = SegTree[v].suffix =
SegTree[v].summa = a[LeftPos];
else
{
int Middle = (LeftPos + RightPos) / 2;
build (a, v*2, LeftPos, Middle);
build (a, v*2+1, Middle+1, RightPos);
Пересчитываем данные в отцовской вершине через информацию в
сыновьях.
SegTree[v] = Merge(SegTree[v*2], SegTree[v*2+1]);
}
}
Вершине v соответствует отрезок [LeftPos;
RightPos]. Функция GetMax вычисляет значения четырех параметров (префикс, суффикс,
сумма, максимальная сумма) на отрезке [Left;
Right] и возвращает
структуру Node, которая их содержит.
struct Node GetMax(int v, int LeftPos, int
RightPos, int Left, int
Right)
{
if ((Left == LeftPos) && (Right == RightPos))
return SegTree[v];
int Middle = (LeftPos + RightPos) / 2;
if (Right <= Middle ) return
GetMax(2*v,LeftPos, Middle,Left,Right);
if (Left > Middle)
return
GetMax(2*v+1,Middle+1,RightPos,Left,Right);
struct Node LeftNode
= GetMax(2*v,LeftPos,Middle,Left,Middle);
struct Node RightNode =
GetMax(2*v+1,Middle+1,RightPos,Middle+1,Right);
return Merge(LeftNode, RightNode);
}
Основная часть программы. Читаем
входные данные. Строим дерево отрезков.
scanf("%d",&n);
for(i = 0; i < n; i++) scanf("%d",&mas[i]);
build(mas,1,0,n-1);
Последовательно обрабатываем m запросов.
scanf("%d",&m);
for(i = 0; i < m; i++)
{
scanf("%d %d",&L,&R);
Res
= GetMax(1,0,n-1,L-1,R-1);
printf("%d\n",Res.max);
}