문제 63
구간 안의 작은 수
길이가 $N$인 정수 수열 $A_1, A_2, \cdots, A_N$이 있다. $Q$개의 쿼리를 순서대로 처리하라.
처음에 $\mathrm{ans}=0$이다. 각 쿼리마다 세 정수 $a$, $b$, $c$가 주어지며 다음과 같이 $l$, $r$, $x$를 정한다.
- $l=((a \oplus \mathrm{ans}) \bmod N)+1$
- $r=((b \oplus \mathrm{ans}) \bmod N)+1$
- $x=c \oplus \mathrm{ans}$
만약 $l>r$이면 두 값을 바꾼다. 각 쿼리마다 구간 $A_l, A_{l+1}, \cdots, A_r$에서 $x$ 이하인 원소의 개수를 출력하고 출력한 값이 다음 쿼리의 $\mathrm{ans}$가 된다.
여기서 $\oplus$는 비트 단위 XOR 연산을 의미한다.
입력
첫 번째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 200\,000)$
두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(0 \le A_i < 2^{30})$
세 번째 줄부터 $Q$개의 줄에 걸쳐 세 정수 $a$, $b$, $c$가 공백으로 구분되어 주어진다. $(0 \le a, b, c < 2^{30})$
출력
각 쿼리마다 구간에서 $x$ 이하인 원소의 개수를 한 줄에 하나씩 출력한다.
예제 입력 1
5 5 5 1 4 2 3 0 4 3 2 0 1 2 0 6 1 7 2 3 3 2
예제 출력 1
3 2 2 0 1
공식 해설
질의가 이전 답으로 암호화되어 있으므로 순서를 바꾸어 처리할 수 없다. 대신 수열은 변하지 않으므로 구간마다 정렬된 원소들을 전처리하는 Merge Sort Tree를 사용한다.
세그먼트 트리의 리프에는 원소 하나를 저장하고, 부모에는 두 자식의 배열을 병합하여 정렬된 배열을 저장한다. 한 원소가 트리의 각 높이에서 한 번씩 들어가므로 전체 저장량은 $O(N\log(N+1))$이다.
질의 구간 $[l,r]$을 겹치지 않는 $O(\log(N+1))$개 노드로 나눈다. 각 정렬 배열에서 이분 탐색으로 $x$보다 큰 첫 위치를 찾는다. 그 앞의 원소 수가 $x$ 이하인 원소 수이며, 그런 위치가 없으면 배열의 모든 원소를 센다. 이를 더하면 구간의 모든 원소를 중복 없이 센다. 같은 값도 등장 횟수만큼 포함된다.
$l,r,x$는 모두 이전 답으로 복원한 뒤 $l>r$이면 두 값을 바꾼다. 현재 답을 구한 뒤에만 다음 질의에 사용할 답을 갱신한다. 초기 답은 $0$이다.
전처리 시간은 $O(N\log(N+1))$, 질의 시간은 $O(\log^2(N+1))$이므로 전체 시간복잡도는 $O(N\log(N+1)+Q\log^2(N+1))$이다. 공간복잡도는 $O(N\log(N+1))$이다.
구현 · 언어별 풀이
C++ 구현
각 노드의 정렬 배열을 vector<int>로 저장하고 부모는 merge로 만든다. 포함된 노드에서는 upper_bound(v.begin(), v.end(), x) - v.begin()을 더한다. 복원식의 XOR은 ^이며, 세 입력을 모두 이전 답으로 복원한 뒤 현재 답을 갱신한다.
C 구현
노드별 정렬 배열을 두 자식의 배열을 선형 병합하여 만든다. 질의 노드에서는 첫 번째 x 초과 위치를 직접 이분 탐색한다. 이전 답으로 xor한 뒤 현재 질의를 처리하고, 질의를 재정렬하지 않는다.
Python 구현
정렬된 노드 리스트에서 bisect_right(values,x)로 x 이하 개수를 구한다. 구축은 두 정렬 리스트의 선형 병합으로 한다. 질의가 이전 답에 의존하므로 Mo 알고리즘처럼 오프라인 정렬할 수 없다.
Java 구현
노드별 int[] 정렬 배열과 upper bound 이분 탐색을 사용한다. Arrays.binarySearch 결과는 중복의 마지막 위치가 아니므로 그대로 개수로 쓰지 않는다. 입력 세 수를 이전 답과 xor한 뒤 구간을 정한다.
Rust 구현
노드별 Vec<i32>를 선형 병합하고 partition_point(|v| *v <= x)로 개수를 센다. 이전 답 xor를 먼저 적용하고 원래 질의 순서를 유지한다.
JavaScript 구현
각 세그먼트 트리 노드의 정렬된 값 목록을 Int32Array로 보관한다. 값은 $2^{30}$ 미만이므로 부호 있는 $32$비트에도 들어간다. 두 자식 목록을 두 포인터로 합치면 노드별 정렬을 반복하지 않고 $O(N\log N)$에 만든다.
복호화의 a ^ last·b ^ last·c ^ last는 모든 입력과 이전 답이 $2^{30}$ 미만이라 JS의 $32$비트 XOR로 정확하다. 복호화 뒤의 인덱스 보정과 두 끝점 정렬은 지문에 맞춰 수행한다.
노드 목록에서 $x$ 이하 값의 마지막 다음 위치를 upper bound로 찾고 목록 길이에서 그 위치를 뺀다. 질의가 이전 답에 의존하므로 원래 순서로 처리해야 하며 Mo 정렬로 바꾸지 않는다. 각 질의는 $O(\log^2 N)$이다.