시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB130665774.026%

문제

음이 아닌 정수만으로 이루어진 길이가 $N$인 수열 $A_0$, $A_1$, $\cdots$, $A_{N-1}$이 주어진다. 이 때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

  • 1 l r x: $l \le \left( i \oplus x \right) \le r$과 $0 \le i < N$을 모두 만족하는 모든 정수 $i$에 대해, $A_i$의 값들을 전부 bitwise XOR하여 출력한다. 단, 해당하는 $i$가 없을 경우 $0$을 출력한다.
  • 2 i x: $A_i$를 $A_i \oplus x$로 설정한다.

$\oplus$는 bitwise XOR 연산자이다. 인덱스가 $0$부터 시작함에 유의하라.

입력

첫 번째 줄에 수열의 길이 $N$이 주어진다.

두 번째 줄에 $N$ 개의 정수 $A_0$, $A_1$, $\cdots$, $A_{N-1}$이 공백으로 구분되어 주어진다.

세 번째 줄에 쿼리의 수 $Q$가 주어진다.

다음 $Q$ 개의 줄의 각 줄에 쿼리가 주어진다. 각 쿼리는 1 l r x 또는 2 i x 중 한 가지 형식이다.

출력

$1$번 쿼리가 주어질 때마다 각 줄에 답을 출력한다.

제한

  • $1 \le N, Q \le 200\,000$
  • $0 \le A_i < 2^{31}$ ($0 \le i < N$)
  • $1$번 쿼리에서, $0 \le l \le r < N$이고 $0 \le x < N$
  • $2$번 쿼리에서, $0 \le i < N$이고 $0 \le x < 2^{31}$
  • $1$번 쿼리는 $1$개 이상 주어진다.
  • 입력으로 주어지는 모든 수는 정수이다.

예제 입력 1

5
1 3 5 4 5
5
1 0 4 0
1 0 2 1
2 0 15
1 4 4 4
1 0 4 1

예제 출력 1

6
6
14
12

노트

  • $a$와 $b$의 bitwise XOR인 $a \oplus b$는, 2진법으로 표현했을 때 $a$와 $b$의 $i$ 번째 자리가 같으면 $a \oplus b$의 $i$ 번째 자리가 $0$이고, 서로 다르면 $1$이 되도록 계산한다.

출처

Contest > Good Bye, BOJ > Hello, BOJ 2022! D번