직사각형 칠하기

시간 제한12초메모리 제한1024 MB

요약

무한 격자에서 가로로 이어진 칸들을 검게 칠하고, 주어진 x 구간에서 아래부터 모두 검은 칸이 이어지는 가장 큰 높이를 구합니다. 질의는 이전 답으로 암호화되어 있어 온라인으로 처리합니다.

난이도: 어려움10점 중 8점
유형: 세그먼트 트리, 구현
정답자: 아직 제출이 없습니다

문제

왼쪽, 오른쪽, 위쪽으로 끝없이 뻗은 격자가 있다. $x \in \mathbb{Z}$ 이고 $y \ge 0$ 인 모든 칸 $(x, y)$ 가 존재한다. 처음에는 모든 칸이 흰색이다. $q$ 개의 쿼리를 처리해야 하며, 쿼리는 두 종류이다.

$y_i$ $l_i$ $r_i$ : $l_i \le x \le r_i$ 를 만족하는 모든 칸 $(x, y_i)$ 를 검은색으로 칠한다. 이미 검은색인 칸은 색이 바뀌지 않는다.
$l_i$ $r_i$ : $x$ 좌표가 $[l_i; r_i]$ 에 속하는 모든 칸을 본다. 바로 아래의 칸이 모두 검은색인 가장 높은 칸을 찾는다. 형식적으로는, $x \in [l_i; r_i]$ 인 $x$ 가 존재하고 모든 $y \in [0;h)$ 에 대해 칸 $(x, y)$ 가 검은색이 되는 최대의 $h$ 를 구한다.

쿼리는 이전 답을 이용해 암호화되어 있으므로 온라인으로 처리해야 한다.

입력

첫 줄에 쿼리의 개수 $q$ ( $1 \le q \le 10^{5}$ )가 주어진다.

이어지는 $q$ 개의 줄에는 암호화된 쿼리가 하나씩 주어진다. $S$ 를 지금까지 처리한 2번 쿼리들의 답의 합이라고 하자. 각 쿼리는 $1$ $(y_i \oplus S)$ $(l_i \oplus S)$ $(r_i \oplus S)$ 또는 $2$ $(l_i \oplus S)$ $(r_i \oplus S)$ 형식이다. 복호화한 값은 $0 \le y_i \le 2 \cdot 10^{5}$ , $0 \le l_i \le r_i \le 2 \cdot 10^{5}$ 를 만족한다. 입력 값은 32비트 정수에 들어가지 않을 수도 있다.

2번 쿼리를 처리할 때마다 새 답을 $S$ 에 더한다.

출력

2번 쿼리마다 답을 한 줄에 하나씩 출력한다.

힌트

S	암호화	쿼리	답
0	1 0 1 1	1 0 1 1	-
0	2 0 10	2 0 10	1
1	1 1 9 9	1 0 8 8	-
1	1 0 0 6	1 1 1 7	-
1	1 0 3 9	1 1 2 8	-
1	2 5 5	2 4 4	0
1	1 1 5 5	1 0 4 4	-
1	2 5 5	2 4 4	2
3	2 0 5	2 3 6	2
5	1 7 6 3	1 2 3 6	-

예제1

예제 1

입력

예상 출력