원숭이와 사과나무

시간 제한2초메모리 제한256 MB

요약

이전 답변만큼 이동한 구간을 조회하고 구간 단위로 사과를 익히며 방문마다 익은 나무 수를 셉니다.

난이도: 보통10점 중 7점
유형: 세그먼트 트리, 구간
정답자: 아직 제출이 없습니다

문제

강을 따라 사과나무가 줄지어 서 있고, 1번부터 차례로 번호가 붙어 있다. 원숭이 크리스는 가끔 이 숲에 와서 번호가 연속한 사과나무 구간을 하나 고르고, 그 구간에서 빨갛게 익은 사과가 달린 나무의 수를 센다. 크리스가 다시 오기 전에, 연속한 몇 그루의 사과가 한꺼번에 익기도 한다.

크리스가 올 때마다 그가 고른 구간에 익은 사과나무가 몇 그루 있는지 구하라. 처음에는 어떤 사과도 익지 않은 상태다.

입력

첫째 줄에 사건의 개수 $M$ 이 주어진다 ( $1 \le M \le 100000$ ). 다음 $M$ 개의 줄에는 사건이 하나씩 주어지며, 각 줄은 세 정수 $D_i$ , $X_i$ , $Y_i$ 로 이루어진다 ( $1 \le D_i \le 2$ , $X_i \le Y_i$ ). $D_i = 1$ 이면 크리스가 온 사건이고, $D_i = 2$ 이면 고른 구간의 사과가 모두 익는 사건이다. 나머지 두 수 $X_i$ 와 $Y_i$ 는 사건의 구간을 나타낸다.

구간의 양 끝은 추가로 관리하는 수 $C$ 로 정해진다. 처음에 $C = 0$ 이다. $i$ 번째 사건의 구간은 $X_i + C$ 번 나무부터 $Y_i + C$ 번 나무까지이며 양 끝을 포함한다. 항상 $1 \le X_i + C$ 이고 $Y_i + C \le 10^9$ 임이 보장된다.

사과가 익는 사건에서는 $C$ 가 바뀌지 않는다. 크리스가 온 사건에서는 그 결과로 $C$ 가 그가 센 익은 사과나무의 수가 된다.

출력

크리스가 올 때마다 그 답을 한 줄에 하나씩 출력한다.

예제3

예제 1
입력
```
3
2 5 8
2 7 10
1 1 10
```
예상 출력
```
6
```
예제 2
입력
```
4
2 2 3
1 1 3
2 2 3
1 -1 3
```
예상 출력
```
2
4
```

예제 3

입력

예상 출력

3
2
0