인덱스국 선발고사 III (Team Selection III)

문제

인덱스국 선발고사 : Day 3

아래 대화는 12월 16일 새벽, IOJ Slack에서 등장한 충격적인 발언의 일부이다.

• IOJ Slack, 12/16

인덱스국의 조교장 앤디는 위 대화를 보고 큰 충격을 받고, 선발고사에 수열과 쿼리 문제를 내기로 결정했습니다. 앤디는 IOJ의 수열과 쿼리 문제들을 모두 검토하여 모든 문제가 N, Q ≤ 100,000이라는 큰 공통점을 발견하였고, 베꼈다는 의혹을 받지 않기 위해 N과 Q 제한을 100,000 으로 내기 않기로 결정했습니다. 앤디는 조교들에게 문제를 내도록 시켰으나, 인덱스 트리로 맨날 최대 최소 합이나 구하던 인덱스국의 조교들은 3가지 문제밖에 내지 못했다고 합니다. 앤디는 어쩔 수 없이 다른 대회 문제를 베껴오기로 했고, 최근 모 대학교 대회에서 출제된 XOR 문제를 쿼리 문제로 바꾸기로 했습니다. 앤디는 조교들을 소집하여 이 문제를 어떻게 바꿀지 회의하였고, 다음과 같은 의견들이 나왔습니다.

• wili19 : L번째 원소부터 R번째 원소까지만 사용했을 때의 쿼리를 주자.
• rickmcoy : XOR의 최대를 구하는 대신 XOR해서 v를 만들 수 있는지 물어보자.
• CokieHCl : 수열을 중간에 바꾸자. 앤디는 위의 의견들을 모두 수합하여 다음과 같은 문제를 만들었습니다.

음이 아닌 정수로 이루어진 수열 $a$가 있습니다. 다음 두 가지 쿼리를 각각 Q1, Q2개 처리하세요.

• $a_x$를 v로 바꿉니다.
• 집합 $\{0, a_l, a_{l+1}, \cdots, a_r\}$의 원소들에서 몇 개를 골라 XOR하여 v를 만들 수 있는지 확인합니다.

구현 세부 사항

다음 함수들을 구현하세요.

void init(int A[])

• 이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.
• A는 크기 N의 배열입니다. 모든 1 ≤ i ≤ N에 대해 $a_i$ = A[i − 1]입니다.

void update(int x, int v)

• 이 함수는 Q1번 그레이더에 의해 호출됩니다.
• 이 함수가 호출된 후 $a_x$ = v가 됩니다.

int query(int l, int r, int v)

• 이 함수는 Q2번 그레이더에 의해 호출됩니다.
• 이 함수는 집합 $\{0, a_l, a_{l+1}, \cdots, a_r\}$의 원소들을 XOR하여 v를 만들 수 있을 경우 1, 아닐 경우 0을 반환해야 합니다.

제한 조건

• 1 ≤ N ≤ 50,000
• 1 ≤ Q1, Q2 ≤ 5,000
• 1 ≤ x, l, r ≤ N , l ≤ r
• 0 ≤ A[i], v < $2^30$ (0 ≤ i ≤ N − 1)

서브태스크

서브태스크	점수	제한 조건
1	2	N, Q2 ≤ 20
2	3	A[i], v < 32 (0 ≤ i ≤ N − 1)
3	5	추가 제한 조건 없음

예제 입출력

N = 4, Q1 = 1, Q2 = 2, A = [1, 2, 4, 8]

그레이더는 다음과 같이 함수를 호출합니다.

init([1, 2, 4, 8])

query(1, 3, 5) = 1

update(3, 8)

query(1, 3, 5) = 0

샘플 그레이더

Sample grader는 다음의 형식으로 입력을 받습니다.

• line 1 : N Q1 Q2
• line 2 : A[0] A[1] ··· A[N − 1]
• line 3 + i (0 ≤ i ≤ Q1 + Q2 − 1) : 1 x v (update(x, v)) or 2 l r v (query(l, r, v))