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

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

HotLog


 

Двумерный Фенвик

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

Есть квадратная клетчатая плоскость, состоящая из n×n клеток (1 ≤ n ≤ 1000). Изначально в каждой клетке записано значение ноль. Ваша задача – написать программу, умеющую отвечать на следующие запросы:

add x y – увеличить значение в ячейке (x, y) на 1.

rsq x1 y1 x2 y2 – вернуть сумму значений в прямоугольнике с углами в (x1,y1) и (x2,y2) соответственно.

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

В первой строке входного файла INPUT.TXT содержится два числа: n и k – размер доски и число запросов соответственно. Следующие k строк содержат сами запросы. Гарантируется, что общее число запросов не превосходит 105. Все координаты - целые числа от 1 до n включительно.

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

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

Пример

INPUT.TXTOUTPUT.TXT
15 15
add 1 1
add 2 2
add 3 3
add 4 4
add 5 5
add 1 5
add 2 4
add 3 3
add 4 2
add 5 1
rsq 1 1 5 5
rsq 2 1 5 5
rsq 1 2 5 5
rsq 2 2 4 4
rsq 3 3 3 3
10
8
8
6
2

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

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

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