[백준] 13504. XOR 합

https://www.acmicpc.net/problem/13504

요약

• 주어진 수열의 연속한 부분수열의 xor합이 가장 큰 것을 구함

접근법 - 실패

• trie(xor) + 분할정복
• merge하면서 중심에서 시작해서 왼쪽의 모든 경우에 대해 xor을 구하고
• 중심에서 시작해서 오른쪽의 모든 경우의 xor에 대해서 큰 값을 찾는 접근법
• $O(N*logN*30 * T) = 100000 * 17 * 30 * 10 = 5억$
• 시간복잡도로 될 줄 알았는데 상수 시간이 많이 소모되었음
• 97%정도에서 시간초과....

접근법 - 성공

• 다른 풀이를 참고
• trie(xor)
• 값을 누적 xor시키면서 값들을 trie에 저장시킴
• 현재 누적한 값과 trie에 있는 값으로 최대 xor을 찾음
  • 이유는
  • $\{e_0, e_1, e_2, ..., current\}$
  • 누적한 값이 $x_0, x_1, x_2, ...$이고, 현재 xor 값을 $c$라고 하면
  • $x_0 \oplus c = e_1 \oplus e_2 \oplus ... current$
  • $x_1 \oplus c = e_2 \oplus e_3 \oplus ... current$
  • 결과적으로 현재위치까지의 모든 부분 수열의 xor중 큰 값을 구할 수 있음
• 이런 현재까지의 부분합을 이용해서 최대 부분수열 접근법이 다른 문제에서도 있었음..