--->
1 задач
<---
Страница:
1
Отображать по:
#1638
Темы:
[Дерево отрезков, RSQ, RMQ]
Ограничение по времени: 0.2 секунды
На планете Олимпия рабочие строят новую дамбу. Часть плоскости, на которой проводятся строительные работы, имеет вид прямоугольника размером 1 x \(L\) метров, на котором введены координаты, как показано на рисунке.
Для поднятия ландшафта используют специально разработанные магические импульсаторы. Если магический импульсатор силой \(H\) поставить в точку с \(X\)-координатой \(p\), то в каждой точке \(q\) отрезка [\(p\)–\(H\);\(p\)] на оси \(X\) рельеф поднимается на \(q\)–\(p\)+\(H\) метров по всей его ширине (то есть для произвольного \(Z\) от 0 до 1), а в каждой точке \(q\) отрезка [\(p\);\(p\)+\(H\)] рельеф поднимается на \(H\)+\(p\)–\(q\) метров по всей его ширине, в остальных точках ландшафт остается неизменным (см. рисунок).
Во время строительства рабочие время от времени интересуются объёмом части дамбы, находящейся над некоторым прямоугольником.
Напишите программу, которая поможет рабочим в их расчётах.
Входные данные
В первой строке входного файла содержатся два целых числа: N – количество операций, которые будут выполнять рабочие (1≤\(N\)≤100000), и \(L\) – длина прямоугольника (1≤\(L\)≤100000).
В следующих \(N\) строках содержатся описания операций: первое число строки – номер операции, где „1” означает, что рабочие собираются поставить магический импульсатор, „2” – рабочие хотят узнать некоторый объём. Если операция имеет код „1”, то далее идут два целых числа \(p\) и \(H\) (0≤\(p\)≤\(L\); 1≤\(H\)≤\(L\)), то есть импульсатор силой \(H\) ставят в позицию p (на оси \(X\)). Если операция имеет код „2”, то далее идут два целых числа \(A\) и \(B\) (0≤\(A\)<\(B\)≤\(L\)); это означает, что рабочие хотят узнать объём части дамбы, которая находится над прямоугольником от \(A\) до \(B\) по оси \(X\), и от 0 до 1 по оси \(Z\).
Выходные данные
Создайте выходной файл, в котором для каждой операции, указанной во входном файле, выведите строку со следующей информацией.
Если операция есть „1”, то выведите число „-1” без кавычек. Если операция есть „2”, то выведите число округленное вниз до ближайшего целого, равное объёму части дамбы, которая находится над прямоугольником от \(A\) до \(B\) по оси \(X\), и от 0 до 1 по оси \(Z\), как показано на рисунке.
Примеры
Входные данные
2 13 1 7 5 2 5 9
Выходные данные
-1 16
Страница:
1
Отображать по:
Выбрано
:
|