e-olymp
Yarışlar

Segment Tree - Multiple Update

Дима и массив

Мама подарила мальчику Диме массив длины n. Массив этот не простой, а особенный. Дима может выбрать три числа - i, j и d (1ijn, -1000d1000), и все элементы с индексами от i до j магически становятся равными d. Дима играет со своим массивом, а мама время от времени задает ему вопросы - какова сумма всех чисел в массиве с индексами от f до t? Дима легко справился с этими вопросами, сможете ли Вы?

Входные данные

В первой строке находятся два целых числа n и q (1n5 * 105, 1q105) - количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано n чисел a1, a2, ..., an (-1000ai1000) - начальное состояние массива. В следующих q строках заданы операции и запросы. Первый символ в строке может быть = или ?. Если строка начинается с =, то это операция присваивания. Далее следуют i, j и d, ограничения на которые заданы выше. Если строка начинается с ?, то это запрос. Далее следуют числа f и t (1f, tn).

Выходные данные

Для каждого запроса выведите сумму чисел в массиве с индексами от f до t, по одному результату в строке.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3 3
1 2 3
? 1 3
= 2 3 2
? 1 3
Çıxış verilənləri #1
6
5
Müəllif Егор Куликов
Mənbə Зимняя Школа Харьков 2012