Обезьяна и яблони
Обезьяна и яблони
Всем известно, что самый вкусный фрукт на земле - это яблоки. Знает это даже обезьяна Крис. Яблоки растут в лесу, в котором есть много яблонь, расположенных вдоль реки и пронумерованных последовательно начиная с 1. Иногда Крис приходит в лес, проходит несколько стоящих подряд яблонь (выбранный им интервал) и считает количество яблонь со спелыми яблоками среди них. Кроме того, бывает так, что к его очередному приходу на нескольких рядом стоящих яблонях уже созрели яблоки.
Для каждого прихода Криса нужно сказать, сколько яблонь с созревшими яблоками находятся в выбранном им интервале. В начале все яблони не созревшие.
Входные данные
В первой строке дается целое число m (1 ≤ m ≤ 100000) - количество событий. Следующие m строк содержат описания событий - по три целых числа di
, xi
, yi
(1 ≤ di
≤ 2, xi
≤ yi
). Если первое число di
= 1, то описываемое событие - это приход Криса, а если di
= 2 - созревание яблок на яблонях. Остальные два числа xi
и yi
, описывают интервал для события.
В вычислении границ интервала также участвует число с, изначально равное 0. Интервал для события - это интервал от xi
+ c до yi
+ c включительно. Гарантируется, что 1 ≤ xi
+ c, yi
+ c ≤ 109
. Если событие - это созревание яблок, то значение c не меняется, а если приход Криса, то в подсчете границ интервала участвует предыдущее значение c, а в результате c становится равным количеству яблонь с созревшими яблоками в указанном интервале.
Выходные данные
Для каждого прихода Криса выведите одну строку, содержащую одно число, - ответ к задаче.
3 2 5 8 2 7 10 1 1 10
6
4 2 2 3 1 1 3 2 2 3 1 -1 3
2 4
6 2 1 7 2 10 12 1 7 11 2 11 13 1 8 10 1 15 17
3 2 0