Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Дерево Фенвика

(Время: 1 сек. Память: 16 Мб Сложность: 45%)

Секретная корпорация, занимающаяся поиском инопланетных жизненных форм обнаружила на одной из планет созвездия Альфа удивительные живые организмы (даже не плоские, а одномерные). Она приняла решение вести наблюдение за развитием и изменением численности организмов, с этой целью на орбиту планеты был послан спутник - наблюдатель, который мог следить за изменениями численности организмов. Недостаток этого «наблюдателя» в том, что он может отслеживать изменения только на той территории планеты, которая находиться непосредственно под ним.

С этой целью его траектория была разбита на равные интервалы. Они пронумерованы от 1 до N. По запросу с Земли о количестве живых форм в интервале с L по R (L ≤ R) - спутник должен, пролетая над ними (L, L+1, …,R-1, R интервалами) произвести подсчет и затем, в ответ на запрос, отправить полученные данные. Но количество организмов постоянно изменяется: в некоторое время в X интервале на Y единиц.

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

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

Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – количество интервалов и запросов соответственно. В последующих M строках расположены запросы в следующем формате:

add X Y – изменение числа организмов в интервале с номером X на Y единиц;

rsq L R – запрос суммарного количества организмов с L по R интервал.

Все числа во входных данных не превосходят 105 по абсолютной величине.

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

В выходной файл OUTPUT.TXT для каждого запроса суммы в отдельной строке выведите результат.

Примеры

INPUT.TXTOUTPUT.TXT
12 3
add 1 4
rsq 1 1
rsq 1 1
4
4
24 8
rsq 1 4
add 1 3
add 4 2
rsq 2 4
rsq 1 2
add 4 -2
add 2 8
rsq 1 4
0
2
3
11

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Статические RSQ и RMQ
 Sqrt-декомпозиция
 Дерево Фенвика
 Дерево отрезков
 A. Дерево Фенвика
 B. Армия
 C. Двумерный Фенвик
 D. Адаптивный поиск
 E. Построение
 F. Карточки - 2

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru



купить виагру с доставкой