만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

수열과 쿼리 25

시간 제한2초메모리 제한512 MB

요약
2^20 미만의 값을 가진 배열에서 구간 비트 AND, 구간 비트 OR 갱신과 구간 최댓값 질의를 처리한다.
난이도

어려움10점 중 8점

유형
세그먼트 트리, 비트 연산, 연결 리스트, 구현
정답자
아직 제출이 없습니다

문제

길이가 NN인 수열 A1,A2,…,ANA_1, A_2, \ldots, A_N이 주어진다. 다음 쿼리를 수행하는 프로그램을 작성하시오.

  • 1 L R X: 모든 L≤i≤RL \le i \le R에 대해서 Ai=Ai∧XA_i = A_i \land X를 적용한다.
  • 2 L R X: 모든 L≤i≤RL \le i \le R에 대해서 Ai=Ai∨XA_i = A_i \lor X를 적용한다.
  • 3 L R: max⁡(AL,AL+1,…,AR)\max(A_L, A_{L+1}, \ldots, A_R)을 출력한다.

∧\land는 비트 AND, ∨\lor는 비트 OR이다.

입력

첫째 줄에 수열의 크기 NN이 주어진다. (1≤N≤200,0001 \le N \le 200,000)

둘째 줄에는 A1,A2,…,ANA_1, A_2, \ldots, A_N이 주어진다. (0≤Ai<2200 \le A_i < 2^{20})

셋째 줄에는 쿼리의 개수 MM이 주어진다. (1≤M≤200,0001 \le M \le 200,000)

넷째 줄부터 MM개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. (1≤L≤R≤N1 \le L \le R \le N, 0≤X<2200 \le X < 2^{20}) 3번 쿼리는 한 번 이상 주어진다.

출력

3번 쿼리의 결과를 한 줄에 하나씩 출력한다.

힌트

수열의 변화는 다음과 같다.

  • 1, 3, 2, 5, 4
  • 5, 3, 2, 5, 4
  • 5, 3, 2, 5, 4
  • 4, 2, 2, 4, 4
  • 4, 2, 3, 5, 4
  • 4, 2, 3, 5, 4
  • 4, 6, 7, 5, 4
  • 4, 6, 7, 5, 4

예제1

  1. 예제 1

    입력
    5
1 3 2 5 4
8
3 1 3
2 1 1 5
3 1 3
1 1 4 6
2 3 4 1
3 2 3
2 2 3 4
3 1 5
    예상 출력
    3
5
3
7