21602번 - Array and Easy Queries 서브태스크

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

길이 $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번 쿼리가 적어도 하나 주어집니다.