DWARFLOG - Manipulate Dwarfs

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 have heights 1, 2, ..., N (each exactly once) and initially all are standing in sorted order with height from 1 to N. Now Snow White play on them by issuing commands of the form:

• 1 X Y -- dwarves with height 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 contiguous subsequence 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). 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”.



Input :

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

Output :




hide comments
smso: 2018-09-14 07:54:06

" contiguous subsequence of the current line" is vague: should be "consecutive ..., irrespective of order and indices"

Rishav Goyal: 2015-12-19 23:40:43


@SourSpinach @Mitch Schwartz @Francky @Tjandra Satria Gunawan @SpojAdmins : Important notice :: This guy (mukesh227194) is constantly being spoiler on Spoj. I think he was banned from Spoj few months back or all his submissions were removed , but he again submitted them all or many and got World Rank#14. i checked his solution for 'DWARFLOG' problem created by me (submission code : 15896226) with another solution with submission id : 15369442. both are same. please remove such spoil from Spoj as they are spoiling others fun.


RE (SourSpinach): Thanks for the report, action has been taken.

Last edit: 2015-12-21 15:56:53
Hugo Hideki Yamashita [Unicamp]: 2015-08-17 01:02:21

@gj2227 the problem says the form "2 A B" has (1 ≤ A ≤ B ≤ N) so your test case is invalid

gj2227: 2015-08-15 05:46:19

plzz tell me the expected output for the following test case
4 6
1 1 6
2 6 1
2 2 5
2 5 2
1 1 2
2 3 5

It should be

Last edit: 2015-08-15 05:48:03
Akhilesh Anandh: 2015-08-09 08:12:42

Time limit is quite strict...

Last edit: 2015-08-09 16:46:00
gamer496: 2015-08-01 10:09:51

Is there any other approach except using advanced ds (fenwick,segment)

reply(author) -> i dont think its possible for a human programmer , saying specifically for this problem as a human programmer. ;-p

Last edit: 2015-08-01 17:14:41
eagle93: 2015-07-28 09:06:27

Is there a better solution than O(n log^2 n)?

reply( @author ) -> yes. there is a very simple algorithm better than (logn) ^2.

Last edit: 2015-07-28 13:19:20
:.Mohib.:: 2015-07-26 21:09:47

really a very learning problem for me..!!

Soma: 2015-07-24 17:02:31

can some one explain me what does the line : "(not necessarily in that order) occupy a contiguous subsequence of the current line" mean?

Pranjal Shankhdhar: 2015-07-23 18:34:30


Added by:Rishav Goyal
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY