EduBrick

Точки в прямоугольнике

2500 мс · 256 МБ · всё или ничего

Обрабатывайте запросы: + x y — поставить точку с координатами (x,y)(x, y); ? x1 y1 x2 y2 — сколько точек лежит в прямоугольнике [x1,x2]×[y1,y2][x_1, x_2] \times [y_1, y_2] включительно.

Формат ввода

В первой строке — число запросов qq (1≤q≤1051 \le q \le 10^5). Далее qq запросов; 1≤x,y≤10001 \le x, y \le 1000, 1≤x1≤x2≤10001 \le x_1 \le x_2 \le 1000, 1≤y1≤y2≤10001 \le y_1 \le y_2 \le 1000.

Формат вывода

На каждый запрос ? выведите количество точек.

Примеры

ввод
5
+ 2 2
+ 3 1
? 1 1 3 3
? 2 2 2 2
? 1 1 1 1
вывод
2
1
0
ввод
2
? 1 1 1000 1000
+ 1000 1000
вывод
0
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.