| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 13 | 3 | 3 | 25.000% |
В чемодане Ньюта Саламандера находится $n$ волшебных животных и столько же отделений для них. Отделения пронумерованы от $1$ до $n$. В каждое отделение помещается ровно одно животное. У каждого существа есть уровень опасности $t$. Как известно, животные весьма активны. Они не любят находиться в одном месте и поэтому постоянно меняются местами внутри чемодана.
Назовём группу подряд идущих животных, которые находятся в отделениях с $l$ по $r$, отрезком.
В течение $m$ минут происходило два типа событий:
Вы узнали, какие события происходили в чемодане, а также начальное положение животных. Найдите ответы на вопросы учёного.
В первой строке задано число $n$ и $m$ --- количество клеток и количество запросов ($1 \le n \le 10^6$; $1 \le m \le 2 \cdot 10^3$).
Во второй строке задана последовательность чисел $t_i$ длины $n$ --- силы животных ($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$).
Для каждого запроса второго типа вывести количество подходящих животных.
3 2 1 2 3 1 1 1 3 3 2 2 3 1 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