2907.
Можете ли Вы ответить на эти вопросы - 3
Задана последовательность целых
чисел a1, a2, ..., an (|ai|
≤ 10000, 1 ≤ n ≤
50000). Над ней Вам следует выполнить m
(m ≤ 50000) операций:
·
модифицировать i-ый элемент
последовательности
·
для заданных x и y вывести MAX {ai + ai+1
+ ... + aj, x ≤ i ≤ j ≤ y}
Вход. Первая строка содержит значение n.
Следующая строка содержит n целых
чисел, задающих последовательность a1,
a2, ..., an. Третья строка содержит
число m. Следующие m строк содержат запросы вида:
·
0 x y: изменить ax на y (|y| ≤ 10000).
·
1 x y: вывести MAX {ai + ai+1 + ... + aj, x ≤ i ≤ j ≤ y}
Выход. Для каждого запроса вывести ответ как требуется в задаче.
Пример входа
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3
Пример выхода
6
4
-3
РЕШЕНИЕ
структуры данных – дерево
отрезков
Анализ алгоритма
Для решения задачи следует реализовать
нетривиальное обобщение дерева отрезков. В каждой его вершине будем хранить
четыре величины: сумму summa на этом
отрезке, максимальную сумму prefix среди
всех префиксов этого отрезка, максимальную сумму suffix среди всех суффиксов, а также максимальную сумму max подотрезка на нём. То есть для
каждого отрезка ответ будет предпосчитан не только для него, но и для отрезков,
упирающихся в его левую и правую границы.
В задаче также следует реализовать
модификацию одного элемента последовательности, одновременно с изменением
которого будут пересчитываться все четыре дополнительные величины во всех узлах
дерева отрезков, ведущих от соответствующего листа к корню.
Пример
Рассмотрим массив {2, -1, 4, -2}
и построим из него дерево отрезков. В каждой вершине вычисляем значения
дополнительных величин. В листах дерева их значения равны самому элементу
массива.
Вычислим
суммы элементов на отрезке [1..2]. Для этого следует совершить вызов функции
GetMax(1, 0, 3, 1, 2). Разобъем отрезок [1..2] на два фундаментальных: [1..1] и
[2..2]. Рекурсивно найдем значения величин на каждом их них (они являются
листами, поэтому все значения равны между собой и равны элементу массива),
после чего совершим сборку двух отрезков.
Реализация алгоритма
Дерево отрезков храним в виде массива t структур 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);
}
Вершине v соответствует отрезок [LeftPos;
RightPos]. Функция Update изменяет
значение элемента с индексом pos на Value.
void Update(int v, int LeftPos, int
RightPos, int pos, int
Value)
{
if (LeftPos == RightPos)
{
SegTree[v].max = SegTree[v].prefix = SegTree[v].suffix =
SegTree[v].summa = Value;
return;
}
int Middle = (LeftPos + RightPos) / 2;
if (pos <= Middle) Update(2*v, LeftPos, Middle,
pos, Value);
else
Update(2*v+1, Middle+1, RightPos, pos, Value);
SegTree[v] = Merge(SegTree[v*2], SegTree[v*2+1]);
}
Основная часть программы. Читаем входные данные. Строим
дерево отрезков.
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",&type);
if (type)
{
scanf("%d %d",&L,&R);
Res = GetMax(1,0,n-1,L-1,R-1);
printf("%d\n",Res.max);
}
else
{
scanf("%d %d",&pos,&Value);
Update(1,0,n-1,pos-1,Value);
}
}