구간 XOR 표현 질의
다이아몬드 III의견: 0
길이 \(N\)의 비음수 정수 배열 \(a_1, a_2, \dots, a_N\)이 주어진다. 다음 두 종류의 질의를 처리해야 한다.
-
C l r x: 구간 \(a_l, \dots, a_r\)의 원소들 중 일부(공집합 포함)를 XOR하여 정확히 \(x\)를 만들 수 있으면 \(1\), 아니면 \(0\)을 출력한다. -
M l r x: 구간 \(a_l, \dots, a_r\)의 원소들 중 일부(공집합 포함)를 XOR한 값과 \(x\)를 다시 XOR했을 때 얻을 수 있는 최댓값을 출력한다.
각 질의마다 구간의 기저를 새로 만들면 너무 느리다.
\(1 \le N \le 100{,}000\)
\(1 \le Q \le 100{,}000\)
\(0 \le a_i, x < 2^{30}\)
\(1 \le l \le r \le N\)
첫 줄에 \(N\)과 질의 수 \(Q\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_i\)가 주어진다.
이어서 \(Q\)개의 줄에 각 질의가 C l r x 또는 M l r x 형태로 주어진다.
각 질의에 대한 답을 한 줄에 하나씩 출력한다.
4 4
3 5 6 1
C 1 2 6
C 1 2 4
M 1 4 0
M 2 3 0
1
0
7
6a=[3,5,6,1]. C 1 2 6: 3 xor 5 = 6 가능 ->1. C 1 2 4: 0,3,5,6 중 4 없음 ->0. M 1 4 0: 전체 부분집합 XOR 최댓값. M 2 3 0: {5,6}로 만들 수 있는 최댓값 = 5 xor 6 = 3.
2 3
0 0
C 1 1 0
C 1 2 1
M 1 2 5
1
0
5a=[0,0]. 어떤 부분집합도 XOR이 0뿐. C 1 1 0 ->1. C 1 2 1 ->0. M 1 2 5: 0 xor 5 = 5가 최대 ->5.
riseoj 작성
출처 Original
평가 및 의견
구간 XOR 표현 질의
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구간 XOR 표현 질의