문제 링크
- http://icpc.me/13538
사용 알고리즘
- PST
시간복잡도
- $O(Q log N)$
풀이
매우 유명한 PST 연습 문제입니다.
배열의 “끝”에 x를 추가하는 것은 x 위치에 1을 업데이트하는 것으로 처리해줄 수 있습니다.
배열의 “마지막” k개를 제거하는 것은 최근 k개의 루트 노드를 없애는 것으로 처리해줄 수 있습니다.
[L, R] 구간에서 x보다 작거나 같은 원소의 개수는 [L, R]번째 세그먼트 트리에서 [1, x]구간에 구간합 쿼리를 날리는 것으로 처리를 해줄 수 있습니다.
[L, R] 구간에서 k번째로 작은 수는 평범한 kth 쿼리입니다.
마지막으로, xor해서 가장 큰 값을 찾는 것만 처리하면 되는데, xor해서 가장 커지는 것은 최상위 비트부터 비교하면서 최대한 반대쪽으로 이동하는 것이 당연히 이득입니다. 잘 구현해주면 됩니다.