https://www.acmicpc.net/problem/13538
문제 요약
- 숫자를 추가 1번 (끝에서)
- 숫자를 삭제 여러번 (끝에서)
- 범위 쿼리
- xor 했을때 큰 값
- k번째 작은 값
- 주어진 숫자보다 작거나 같은 개수
- 특징
- 변경은 끝에서만 발생
- 추가는 1회만 가능 ==> 많아야 쿼리수만큼 주어짐
- xor을 이용
접근법
- 찾아보면 Persistent Segment Tree를 이용한다고 함
- trie + xor 처리 + binary search(lower, upper)로 풀었음
- trie
- 숫자를 비트로 바꾸어서 문자열 처리(최대 19자리)
- 노드에 원소의 번호도 추가함 : 끝에서 변경이 발생하므로 오름차순 정렬된 상태로 추가/삭제가 유지됨
- 삭제시 노드를 순회하면서 마지막 추가한 원소를 삭제함
- 범위 쿼리
- trie 노드를 순회하면서 범위에 몇개가 있는지 파악 가능 : lower_bound, upper_bound
- xor 큰 값
- 범위 내의 노드를 순회하면서
- 주어진 숫자와 반대 값인 노드로 순회함
- 반대값이 있으면.. 그쪽으로 계속 순회
- 없으면.. 어쩔수 없이 순회
- 순회하면서 최종 도달한 값이 구하고자 하는 값임
- k번째 작은 값
- 구간트리, 비트문자열... 많이 사용하던 기법
- 0......으로 시작하는 범위 내의 숫자들의 개수가 크면 / 작으면
- 주어진 숫자보다 작거나 같은 개수
- 앞에서 한 것과 유사함
- 최상위 비트부터 보면서 최상위 비트가 1이면 0....으로 시작 하는 것들은 다 작을 것임
- 그리고 1...로 시작하는 것들은 이후 비트를 보고 더 판단하면 됨
- 최상위 비트가 0이면 0....으로 시작하는 것들 이후 비트를 보고 더 판단하면 됨
- 범위 내에 노드가 존재하는 곳만 따라가는 것을 주의해야함
newbieski