시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
12 초 (추가 시간 없음) 512 MB 182 67 10 12.987%

문제

원래 이 자리에는 킬러 문제가 들어갈 예정이었지만, 다른 문제의 난이도가 예상보다 높은 걸 보고 경악한 브루는 자신과 같은 낮은 실력의 참가자도 즐길 수 있는 쉬운 문제를 만들기로 결심했습니다.

길이 $N$의 수열 $A$가 주어집니다. 이 수열에 아래 네 가지 종류의 쿼리를 처리하는 프로그램을 만들어 봅시다.

  • $1$  $l$  $r$  $x$ : $l \le i \le r$인 모든 $A_i$를 $A_i$  AND  $x$로 바꿉니다.
  • $2$  $l$  $r$  $x$ : $l \le i \le r$인 모든 $A_i$를 $A_i$  OR  $x$로 바꿉니다.
  • $3$  $l$  $r$  $x$ : $l \le i \le r$인 모든 $A_i$를 $A_i$  XOR  $x$로 바꿉니다.
  • $4$  $l$  $r$  $x$ : $l \le i \le r$이고 $A_i = x$인 $i$의 개수를 출력합니다.

이때, AND, OR, XOR은 비트 연산을 의미합니다.

입력

첫 줄에는 수열의 길이 $N$과 쿼리의 수 $Q$가 주어집니다.

둘째 줄에는 수열의 초기 상태 $A_1, A_2, \cdots, A_N$이 주어집니다.

셋째 줄부터 $Q$개의 줄에는 각 쿼리에 대한 정보 $t$  $l$  $r$  $x$가 순서대로 주어집니다.

출력

모든 4번 쿼리에 대해, 그 답을 한 줄에 하나씩 출력합니다.

제한

  • $1 \le N \le 10^6$
  • $1 \le Q \le 10^5$
  • $0 \le A_i < 2^{16}$
  • 모든 쿼리에 대해, $1 \le t \le 4$, $1 \le l \le r \le N$, $0 \le x < 2^{16}$
  • 4번 쿼리가 적어도 하나 주어집니다.

서브태스크

번호 배점 제한
1 30

$N \le 100$, $Q \le 100$

2 10

$A_i = 0$, 모든 쿼리에 대해 $x=0$

3 75

$0 \le A_i \le 1$, 모든 쿼리에 대해 $0 \le x \le 1$

4 75

$0 \le A_i < 2^4$, 모든 쿼리에 대해 $0 \le x < 2^4$

5 110

모든 쿼리에 대해 $l=1$, $r=N$

6 100

추가 제한 조건이 없습니다.

예제 입력 1

3 3
1 1 1
4 1 3 1
2 1 2 2
4 1 3 1

예제 출력 1

3
1

예제 입력 2

10 10
2 5 5 5 0 0 6 4 4 7
4 3 5 0
1 3 5 4
2 2 5 0
2 7 7 0
3 3 5 0
4 1 3 1
3 1 10 2
3 4 9 4
3 1 3 5
4 3 10 6

예제 출력 2

1
0
2

출처

High School > 서울과학고등학교 > 2021 SciCom Qualification Test 1E번

  • 문제를 만든 사람: 79brue

채점 및 기타 정보

  • 예제는 채점하지 않는다.