TRIE
-
[BOJ] 16903 수열과 쿼리 20PS/BOJ 2020. 9. 7. 22:31
https://www.acmicpc.net/problem/16903 16903번: 수열과 쿼리 20 첫째 줄에 쿼리의 개수 M(1 ≤ M ≤ 200,000)이 주어진다. 둘째 줄부터 M개의 줄에 쿼리가 주어진다. 입력으로 주어지는 x의 범위는 109보다 작거나 같은 자연수이다. 3번 쿼리는 하나 이상 주어진다. www.acmicpc.net 알고리즘: Trie 시간복잡도: $O(Mlog10^9)$ 접근: M이 20만으로 꽤 크다. 따라서 매 쿼리마다 빠른 시간 안에(log) 해결해야한다. 여기서 주요 연산이 XOR 라는 것에 주목했다. 어차피 문제가 되는건 3번 쿼리다. (1, 2번은 단순 추가/삭제니...) A에 있는 모든 원소와 XOR 연산을 하고 최댓값을 구해야한다. 두가지 관찰만 하면 풀이에 쉽게 ..