#93 수열과 쿼리 67

Statement

길이 $N$ 의 오름차순으로 정렬된 수열 $A_1, A_2, \dots, A_N$ 이 주어진다.

당신은 이 수열에 대해 $6$ 가지의 갱신 쿼리와 $7$ 가지의 질의 쿼리를 처리해야 한다. 각각의 쿼리는 아래와 같다.

갱신 쿼리는 아래와 같다.

$1\ l\ r\ x$ : $l\le i\le r$ 인 모든 $i$ 에 대해 $A_i \rightarrow A_i+x$ 를 수행한다.
$2\ l\ r\ x$ : $l\le i\le r$ 인 모든 $i$ 에 대해 $A_i \rightarrow \lfloor \frac{A_i}{x} \rfloor$ 를 수행한다.
$3\ l\ r\ x$ : $l\le i\le r$ 인 모든 $i$ 에 대해 $A_i \rightarrow \max(A_i, x)$ 를 수행한다.
$4\ l\ r\ x$ : $l\le i\le r$ 인 모든 $i$ 에 대해 $A_i \rightarrow \min(A_i, x)$ 를 수행한다.
$5\ l\ r$ : 구간 $[l, r]$ 를 한 칸 오른쪽으로 민다. 즉, $l<i\le r$ 인 모든 $i$ 에 대해 $A_i \rightarrow A_{i-1}$ , $A_l \rightarrow A_r$ 을 동시에 수행한다.
$6\ l\ r$ : 구간 $[l, r]$ 를 뒤집는다. 즉, $l\le i\le r$ 인 모든 $i$ 에 대해 $A_i \rightarrow A_{r+l-i}$ 을 동시에 수행한다.

질의 쿼리는 아래와 같다.

$7\ l\ r$ : $A_l, A_{l+1}, \ldots, A_r$ 의 합을 출력한다.
$8\ l\ r$ : $A_l, A_{l+1}, \ldots, A_r$ 의 최솟값을 출력한다.
$9\ l\ r$ : $A_l, A_{l+1}, \ldots, A_r$ 의 최댓값을 출력한다.
$10\ l\ r\ x$ : $A_l, A_{l+1}, \ldots, A_r$ 중 $x$ 이상인 값의 개수를 출력한다.
$11\ l\ r$ : $|A_l-A_{l+1}|+|A_{l+1}-A_{l+2}|+\cdots+|A_{r-1}-A_r|$ 의 값을 출력한다.
$12\ l\ r$ : $A_l, A_{l+1}, \ldots, A_r$ 에 등장하는 서로 다른 값의 개수를 출력한다.
$13\ l\ r$ : $A_l, A_{l+1}, \ldots, A_r$ 의 중앙값, 즉 오름차순으로 정렬했을 때 $\left\lceil\frac{r-l+1}{2}\right\rceil$ 번째 값을 출력한다.

입력은 다음과 같은 형식으로 주어진다.

$N\ Q$ $A_1 \ A_2 \ \cdots \ A_{N}$ $\text{query}_1$ $\text{query}_2$ $\dots$ $\text{query}_Q$

질의 쿼리가 주어질 때마다, 해당 쿼리의 답을 한 줄에 하나씩 출력한다.

입력

출력

67