X or What?
시간 제한40초메모리 제한1024 MB
점 값을 바꿀 때마다 xor 합의 1인 비트 개수가 짝수인 가장 긴 부분 구간의 원소 개수를 구합니다.
문제
Steven에게 음이 아닌 정수 N개로 이루어진 배열이 있다. 배열의 i번째 정수 (0부터 번호를 매긴다)는 Ai이다.
Steven은 xor-even인 부분 구간을 좋아한다. 부분 구간은 인덱스 쌍 (L, R)로 나타내며, 원소 AL, AL+1, ..., AR-1, AR을 가리킨다. 구간의 xor 합은 AL xor AL+1 xor ... xor AR-1 xor AR이고, xor은 비트 단위 배타적 논리합이다.
구간의 xor 합을 이진수로 나타냈을 때 1인 비트의 개수가 짝수이면 그 구간은 xor-even이다.
Steven은 배열을 Q번 수정한다. i번째 수정은 Pi번째 원소 (0부터 번호를 매긴다)를 Vi로 바꾼다. 각 수정 후에 xor-even인 부분 구간 중 원소가 가장 많은 구간의 원소 개수를 구하라.
입력
첫 줄에 테스트 케이스의 개수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 줄에는 원소의 개수 N과 수정 횟수 Q가 주어진다. 둘째 줄에는 N개의 정수가 주어지며, i번째 정수는 Ai이다. 이어서 Q줄에 수정 정보가 주어진다. i번째 줄의 Pi와 Vi는 Pi번째 원소를 Vi로 바꾼다는 뜻이다.
출력
각 테스트 케이스마다 Case #x: y_1 y_2 ... y_Q 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호 (1부터 시작)이고, y_i는 i번째 수정 후 A에서 xor-even인 부분 구간 중 가장 큰 구간의 원소 개수이다. xor-even인 부분 구간이 없으면 0을 출력한다.
제한
1 ≤ T ≤ 100. 0 ≤ Ai < 1024. 0 ≤ Pi < N. 0 ≤ Vi < 1024.
힌트
샘플 1에서 N = 4, Q = 3이다.
- 첫 번째 수정 후 A는 [10, 13, 3, 7]이다. 부분 구간 (0, 3)의 xor 합은 10 xor 13 xor 3 xor 7 = 3이다. 이진수로 3은 11이고 1인 비트가 2개로 짝수이므로, 이 구간은 xor-even이다. 원소 4개를 모두 포함하므로 답은 4이다.
- 두 번째 수정 후 A는 [32, 13, 3, 7]이다. 가장 큰 xor-even 부분 구간은 (0, 2)이고, xor 합은 32 xor 13 xor 3 = 46이다. 이진수로 46은 101110이다.
- 세 번째 수정 후 A는 [32, 13, 22, 7]이다. 가장 큰 xor-even 부분 구간은 다시 (0, 3)이며, xor 합은 32 xor 13 xor 22 xor 7 = 60이다. 이진수로 60은 111100이다.
샘플 2에서 N = 5, Q = 1이다. 첫 번째 수정 후 A는 [14, 1, 15, 20, 26]이다. 가장 큰 xor-even 부분 구간은 (1, 4)이고, xor 합은 1 xor 15 xor 20 xor 26 = 0이다. 이진수로 0에는 1인 비트가 없으므로 답은 4이다.