문제 64
희소한 수열
$A_0, A_1, \cdots, A_{2^{30}-1}$이 모두 $0$인 수열 $A$가 있다. $Q$개의 쿼리를 순서대로 처리하라.
처음에 $\mathrm{ans}=0$이다. 쿼리는 다음 중 하나이다.
1 a b x: $l=a \oplus \mathrm{ans}$, $r=b \oplus \mathrm{ans}$로 정한다. $l>r$이면 두 값을 바꾼다. 그다음 $A_l, A_{l+1}, \cdots, A_r$에 $x$를 더한다. $(0 \le a, b < 2^{30}; 1 \le x \le 1\,000)$2 a b: $l=a \oplus \mathrm{ans}$, $r=b \oplus \mathrm{ans}$로 정한다. $l>r$이면 두 값을 바꾼다. 그다음 $A_l, A_{l+1}, \cdots, A_r$의 최댓값을 출력한다. $(0 \le a, b < 2^{30})$
2 a b 쿼리에서 출력한 값이 다음 쿼리의 $\mathrm{ans}$가 된다.
여기서 $\oplus$는 비트 단위 XOR 연산을 의미한다.
입력
첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 200\,000)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 하나씩 주어진다.
출력
2 a b 쿼리마다 구간의 최댓값을 한 줄에 하나씩 출력한다.
예제 입력 1
7 1 2 5 3 2 0 10 1 0 2 4 2 1 6 1 7 7 2 2 7 7 2 0 3
예제 출력 1
3 7 2 7
공식 해설
필요한 구간만 만들기
길이가 $2^{30}$인 배열 전체를 저장할 수는 없다. 전체 범위를 담당하는 루트에서 시작하여 실제 갱신에 필요한 자식만 만드는 동적 세그먼트 트리를 사용한다.
각 노드에 그 구간 전체에 더한 값 $t$와, 조상의 덧셈을 제외한 구간 최댓값 $m$을 저장한다. 아직 없는 자식의 최댓값은 $0$이다. 다음 관계를 유지한다.
\[
m=t+\max(m_{\mathrm{left}},m_{\mathrm{right}}).
\]
구간 전체에 $x$를 더하면 $t,m$에 모두 $x$를 더한다. 일부만 갱신한다면 겹치는 자식만 만들어 내려가고, 위 식으로 $m$을 다시 계산한다. 부모의 $t$를 자식에게 실제로 내려보낼 필요가 없다.
조회는 조상의 덧셈을 누적하기
질의에서는 조상에 남아 있는 덧셈의 합 $z$를 함께 전달한다. 노드 전체가 질의에 포함되면 $z+m$을 반환한다. 일부만 겹치면 자식에게 $z+t$를 전달한다. 없는 노드에서는 그 구간만의 갱신이 없으므로 겹치는 부분의 값은 모두 $z$이다.
따라서 조회할 때는 노드를 만들 필요가 없다. 겹치지 않는 구간은 무시하며, 이 문제는 초기값이 $0$이고 덧셈이 양수이므로 그 반환값을 $0$으로 두어도 된다.
두 인덱스는 이전 출력값과 XOR하여 복원한 뒤 순서를 맞춘다. 처음 출력값은 $0$이고, 갱신 명령에서는 출력값을 바꾸지 않는다.
트리 높이가 $30$이므로 시간복잡도와 공간복잡도는 $O(Q\log 2^{30})$이다.
구현 · 언어별 풀이
C++ 구현
노드를 vector에 저장하고 두 자식은 인덱스로 가리킨다. 없는 자식은 하나의 공통 인덱스로 표시하고, 조회에서는 새 노드를 만들지 않는다. 분할 과정에서 배열이 늘어나도 유효하도록 자식 필드의 참조 대신 노드 인덱스로 다시 접근한다. 입력 복원에는 ^를 사용한다.
C 구현
동적 트리 노드 풀에 자식 인덱스와 long long max/lazy를 둔다. 갱신이 닿는 노드만 만들고 질의에서는 노드를 생성하지 않는다. 부재 자식의 기본값 0에 부모 lazy를 반영해 계산한다.
Python 구현
넓은 좌표 전체 배열 대신 자식 인덱스·max·lazy의 노드 풀을 둔다. array('i')와 array('q')를 사용하면 노드 객체 비용을 줄일 수 있다. 질의는 누적 lazy를 전달하며 읽기만 하고 새 노드를 만들지 않는다.
Java 구현
int[] left/right와 long[] max/lazy의 확장 가능한 풀을 둔다. 재귀 함수는 노드 인덱스를 받는다. 부재 자식은 값 0에서 시작하지만 조상 lazy는 적용되어야 하며 질의만으로 풀을 늘리지 않는다.
Rust 구현
Vec<Node>에 자식 인덱스와 i64 max/lazy를 저장한다. push나 재귀 전에 필요한 필드를 복사하여 Vec 재할당과 borrow 충돌을 피한다. 질의는 조상 lazy를 들고 내려가며 노드를 생성하지 않는다.
JavaScript 구현
좌표는 $2^{30}$ 미만이며 누적된 증가량은 최대 $200\,000\cdot1\,000=2\cdot10^8$이다. 값과 좌표가 모두 $32$비트 부호 범위 안이므로 복호화 XOR와 Int32Array를 사용할 수 있다. 구간 중간점은 Math.floor((l + r) / 2)로 계산하면 덧셈에 불필요한 비트 변환을 넣지 않아도 된다.
노드에는 자식 번호, 해당 구간 전체의 증가량, 자식 쪽의 상대 최댓값을 보관한다. 아직 없는 자식의 상대 최댓값은 $0$이다. 구간 전체에 더한 값은 부모에 남기고 max = lazy + Math.max(leftMax, rightMax)로 갱신하면 읽기 질의 때문에 새 노드를 만들 필요가 없다.
부분 조회에는 조상 lazy의 누적값을 전달한다. 없는 자식도 이 누적값을 받아야 하며, 겹치지 않는 구간은 결과 후보에서 제외한다. 노드 저장 배열은 필요한 크기로 늘리거나 블록으로 할당해 실제 생성 노드 수에 맞춘다. 전체 $2^{30}$개 위치의 배열은 만들지 않는다.