마법의 가방

시간 제한1.5초메모리 제한1024 MB

요약

n개의 값이 든 배열에서 같은 길이의 두 구간을 맞바꾸는 연산과, 구간 안에서 a 이상 b 이하인 값의 개수를 세는 질의를 처리합니다.

난이도: 어려움10점 중 8점
유형: 배열, 정렬, 이분 탐색, 분할 정복
정답자: 아직 제출이 없습니다

문제

뉴트 스캐맨더의 가방에는 $n$ 마리의 마법 동물과 같은 수의 칸이 있습니다. 칸은 1부터 $n$ 까지 번호가 매겨져 있습니다. 각 칸에는 정확히 한 마리의 동물이 들어 있습니다. 각 생명체에는 위험도 $t$ 가 있습니다. 동물들은 매우 활발해서 한곳에 머무르기를 싫어하고, 그래서 가방 안에서 계속 자리를 바꿉니다.

$l$ 번 칸부터 $r$ 번 칸까지 이어진 동물의 묶음을 구간이라고 합니다.

$m$ 분 동안 두 종류의 사건이 일어났습니다.

길이가 같고 겹치지 않는 두 동물 구간이 자리를 맞바꿉니다. 구간 $l_1$ 부터 $r_1$ 까지가 구간 $l_2$ 부터 $r_2$ 까지와 바뀝니다. 정확히는 $i$ 가 $l_1$ 부터 $r_1$ 까지의 각 값일 때, 칸 $i$ 의 동물이 칸 $i - l_1 + l_2$ 의 동물과 자리를 바꿉니다.
동물학자가 구간 $l$ 부터 $r$ 까지에 있는 동물 가운데 위험도 $t$ 가 $a$ 이상 $b$ 이하인 동물의 수를 묻습니다.

입력

첫 줄에 칸의 수 $n$ 과 질의의 수 $m$ 이 주어집니다 ( $1 \le n \le 10^6$ ; $1 \le m \le 2 \cdot 10^3$ ).

둘째 줄에는 길이 $n$ 의 수열 $t_i$ 가 주어집니다. 이는 각 동물의 위험도입니다 ( $1 \le t_i \le 10^9$ ).

이어지는 $m$ 개의 줄마다 질의의 종류 $type$ 이 먼저 나옵니다 ( $1 \le type \le 2$ ).

$type = 1$ 이면 자리 교환을 나타내는 네 수 $l_1$ , $r_1$ , $l_2$ , $r_2$ 가 이어서 주어집니다. 두 구간은 겹치지 않고 길이가 같습니다 ( $1 \le l_1 \le r_1 \le n$ , $1 \le l_2 \le r_2 \le n$ ).

$type = 2$ 이면 동물학자의 질문을 나타내는 네 수 $l$ , $r$ , $a$ , $b$ 가 이어서 주어집니다 ( $1 \le l \le r \le n$ , $1 \le a \le b \le 10^9$ ).

출력

종류가 2인 각 질의에 대해, 조건을 만족하는 동물의 수를 출력합니다.

예제2

예제 1
입력
```
3 2
1 2 3
1 1 1 3 3
2 2 3 1 2
```
예상 출력
```
2
```

예제 2

입력

6 5
1 2 3 4 5 6
1 1 3 4 6
1 2 3 5 6
2 3 6 2 5
1 1 1 5 5
2 2 5 2 6

예상 출력

2
3