2939.
Дима и массив
Мама подарила
мальчику Диме массив длины n. Массив
этот не простой, а особенный. Дима может выбрать три числа – i, j
и d (1 ≤ i ≤ j ≤ n, -1000 ≤ d ≤ 1000), и все элементы с индексами от i до j магически
становятся равными d. Дима играет со
своим массивом, а мама время от времени задает ему вопросы – какова сумма всех
чисел в массиве с индексами от f до t? Дима легко справился с этими
вопросами, сможете ли Вы?
Вход. В первой строке находятся два целых числа n и q
(1 ≤ n ≤ 5·105,
1 ≤ q ≤ 105) –
количество элементов в массиве и суммарное количество операций и запросов
соответственно. В следующей строке дано n
чисел a1, a2, ..., an (-1000 ≤ ai
≤ 1000) – начальное состояние массива. В следующих q строках заданы операции и запросы. Первый символ в строке может
быть = или ?. Если строка начинается с =, то это операция присваивания. Далее
следуют i, j и d, ограничения на
которые заданы выше. Если строка начинается с ?, то это запрос. Далее следуют
числа f и t (1 ≤ f, t ≤ n).
Выход. Для каждого запроса выведите сумму чисел в массиве с
индексами от f до t, по одному результату в строке.
|
Пример
входа |
Пример
выхода |
|
3 3 1 2 3 ? 1 3 = 2 3 2 ? 1 3 |
6 5 |
РЕШЕНИЕ
структуры данных – дерево отрезков
Анализ алгоритма
Для решения
задачи следует реализовать дерево отрезков, поддерживающее групповое
присваивание и суммирование.
При операции
присваивания предыдущие значения в сыновьях сумм s1 и s2, а также значения отложенных присавиваний a1 и a2 теряются.
Реализация алгоритма
Дерево отрезков храним в векторе SegTree длины 4*MAX, где MAX
– максимальное количество элементов, которое может храниться в дереве отрезков.
#define MAX 500000
#define INF 2100000000
struct node
{
int summa, add;
};
vector<node> SegTree(4*MAX);
vector<int> m;
На вход функции BuildTree построения
дерева отрезков передается массив a, номер текущей вершины дерева v и границы отрезка lpos и rpos, соответствующие
вершине v. Если в вершине v значение add не равно INF, то в ней имеется отложенная операция.
void BuildTree(vector<int>& a, int v, int lpos, int rpos)
{
if (lpos == rpos)
{
SegTree[v].summa = a[lpos];
SegTree[v].add = INF;
}
else
{
int mid = (lpos + rpos) / 2;
BuildTree(a, 2*v, lpos, mid);
BuildTree(a, 2*v+1, mid + 1, rpos);
SegTree[v].summa = SegTree[2*v].summa + SegTree[2*v+1].summa;
SegTree[v].add = INF;
}
}
Функция Push производит проталкивание значения add вершины
v в сыновья. Если add ≠ INF, то его следует протолкнуть на один уровень вниз.
После проталкивания значение add в вершине v ставим
равным INF.
void Push(int v, int lpos, int mid, int rpos)
{
if (SegTree[v].add
== INF) return;
SegTree[2*v].add
= SegTree[v].add;
SegTree[2*v].summa
= (mid - lpos + 1) * SegTree[v].add;
SegTree[2*v+1].add
= SegTree[v].add;
SegTree[2*v+1].summa
= (rpos - mid) * SegTree[v].add;
SegTree[v].add
= INF;
}
Функция Update присваивает элементам с индексами от left до right значение val. Вершине v
соответствует отрезок [lpos; rpos].
void Update(int v, int lpos, int rpos, int left, int right, int val)
{
if (left >
right) return;
Если [left; right] соответствует
отрезку, который хранится в вершине дерева [lpos; rpos], то присваиваем в текущей вершине дерева переменным add и summa соответствующие значения.
if ((lpos == left)
&& (rpos == right))
{
SegTree[v].add
= val;
SegTree[v].summa
= (right - left + 1) * val;
return;
}
Находим середину отрезка mid = (lpos + rpos)
/ 2.
int mid
= (lpos + rpos) / 2;
Проведем проталкивание, если add не равно INF.
Push(v, lpos, mid, rpos);
Рекурсивно обрабатываем левого и правого сына текущей вершины
дерева отрезков.
Update(2*v, lpos, mid, left, min(mid, right), val);
Update(2*v+1, mid+1, rpos, max(left, mid+1), right, val);
Пересчитываем значение суммы в вершине v через значения сумм
ее детей.
SegTree[v].summa = SegTree[2*v].summa + SegTree[2*v+1].summa;
}
Функция Summa
возвращает значение суммы на отрезке [left; right]. Вершине v
соответствует отрезок [lpos; rpos].
long long Summa(int v, int lpos, int rpos, int left, int right)
{
if (left >
right) return 0;
Если [left; right] совпадает с отрезком [lpos; rpos], который хранится в вершине v дерева, то возвращаем находящееся в
ней значение суммы.
if ((lpos == left)
&& (rpos == right))
return
SegTree[v].summa;
Находим середину отрезка mid = (lpos + rpos)
/ 2.
int mid
= (lpos + rpos) / 2;
Проведем проталкивание, если add не равно INF.
Push(v, lpos,
mid, rpos);
Разбиваем отрезок [lpos; rpos] на [lpos; mid] и [mid+1; right]. Запускаем рекурсивно вычисление сумм на подотрезках.
Складываем полученные суммы.
return
Summa(2*v, lpos, mid, left,
min(mid, right)) +
Summa(2*v+1,
mid+1, rpos, max(left, mid+1), right);
}
Основная часть программы. Читаем
входные данные.
scanf("%d
%d",&n,&q);
m.resize(n+1);
for(i = 1; i <= n; i++)
scanf("%d",&m[i]);
scanf("\n");
По данным в массиве m строим дерево
отрезков.
BuildTree(m,1,1,n);
Последовательно обрабатываем q запросов. В зависимости от типа запроса производим либо групповое
присваивание, либо вычисление суммы на отрезке.
for(k = 0; k < q; k++)
{
scanf("%c ",&c);
if (c == '=')
{
scanf("%d %d %d\n",&i,&j,&d);
Update(1,1,n,i,j,d);
} else
{
scanf("%d %d\n",&f,&t);
printf("%d\n",Summa(1,1,n,f,t));
}
}