구간 최대 배타적 논리합
다이아몬드 IV의견: 0
길이 \(N\)의 비음 정수 수열 \(A_1, \dots, A_N\)이 주어진다 (\(0 \le A_i < 2^{20}\)).
\(Q\)개의 질의가 주어진다. 각 질의는 세 정수 \(l\), \(r\), \(x\)로 이루어지며, 구간 안의 원소 중 \(x\)와의 배타적 논리합(XOR)이 최대가 되는 값을 찾아 그 최댓값을 출력해야 한다. 즉 \(\max_{l \le i \le r} (A_i \oplus x)\)를 구하여라.
각 질의마다 구간을 직접 훑으면 \(O(NQ)\)로 통과할 수 없다.
\(1 \le N, Q \le 50{,}000\)
\(1 \le l \le r \le N\)
\(0 \le A_i, x < 2^{20}\)
첫 줄에 두 정수 \(N\), \(Q\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(A_1, \dots, A_N\)이 주어진다.
이어서 \(Q\)개의 줄에 각 질의의 \(l\), \(r\), \(x\)가 주어진다.
각 질의에 대해 \(\max_{l \le i \le r}(A_i \oplus x)\)를 한 줄에 하나씩 출력한다.
4 4
1 5 7 2
1 4 3
2 3 0
1 1 1
3 4 4
6
7
0
6[1,5,7,2], x=3 전체: 13=2,53=6,73=4,23=1 -> 최대 6. [5,7],x=0: 5,7 -> 7. [1,1],x=1: 1^1=0. [7,2],x=4: 74=3,24=6 -> 6.
1 2
0
1 1 0
1 1 1048575
0
1048575원소 0 하나. x=0이면 0^0=0. x=1048575(=2^20-1)이면 0과의 XOR은 1048575.
골드 Iriseoj 작성
출처 Original
평가 및 의견
구간 최대 배타적 논리합
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구간 최대 배타적 논리합