https://www.acmicpc.net/problem/30865
문제 요약
- 수열이 주어지고 두 개의 쿼리
- i 번째 수를 x로 변경
- x와 xor 했을때 i번째로 큰 값 출력
- N = 20만, 쿼리 = 20만, 숫자 : 2^31
접근법
- bit로 바꾸어서 트리에 저장 => trie 비슷
- 하위 노드의 count도 저장
- k번째 xor 찾기
- 구간트리에서 k 번째 수 찾는 알고리즘 => 1을 먼저 보고 0을 그 다음에 볼 것임
- 다만 xor 값을 고려하면 xor 값은 반전이고 그때 그때 먼저 봐야할 노드가 변할 것임
- 찾아가려는 노드의 하위 개수가 k 보다 많은지 적은지를 판단해서 아래로 탐색해나감
- 거쳐간 노드의 bit를 모으고 그 숫자에 x를 xor 한 값이 결과
newbieski