print1952. Snow White

printSnow White

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

In a small village beyond seven hills and seven seas, Snow White lives together with `N` dwarves who spend all their time eating and playing League of Legends. Snow White wants to put an end to this, so she has organized gym classes for them.
At the beginning of each class, the dwarves must stand in line, ordered by their height. For the purposes of this task, assume that the dwarves haveheights 1, 2, …, `N` (each exactly once). However, the dwarves' intelligence has somewhat deterioratedfrom the unhealthy lifestyle, so they are incapable of ordering themselves by height. That's why Snow White helps them by issuing commands of the form:
1 `X` `Y` –- dwarves at positions `X` and `Y` in the line must switch places.
She also checks their ordering by issuing queries of the form:
2 `A` `B` –- do dwarves with heights `A`, `A+1`, …, `B` (not necessarily in that order) occupy a contiguoussubsequence of the current line?
Help the doofus dwarves follow Snow White's instructions and respond to her queries.
The first line of input contains the two positive integers `N` and `M`, the number of dwarves and the number of Snow White's requests, respectively (`2\ ≤\ N\ ≤\ 200\ 000`, `2\ ≤\ M\ ≤\ 200\ 000`).
The following line contains `N` space-separated positive integers from 1 to `N`, each exactly once, representing the initial arrangement of the dwarves.
Each of the following `M` lines contains a single Snow White's request, of the form "1 `X` `Y`" (`1\ ≤\ X,\ Y\ ≤\ N`,`X\ ≠\ Y`) or “2 `A` `B`” (`1\ ≤\ A\ ≤\ B\ ≤\ N`), as described in the problem statement.
The output must contain one line for each request of type 2, containing the reply to the query, either “YES” or “NO”.

Sample Input #1

input 
5 3 
2 4 1 3 5 
2 2 5 
1 3 1 
2 2 5 

Sample Output #1

NO 
YES

Sample Input #2

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

Sample Output #2

YES
NO
YES
NO
YES
Source: COCI 2012/2013, Croatian olympiad
loading