DRWLNS  Drawing Lines
John is a bit upset now. Today was his chemistry central viva and it did not go very well. So to cheer up he bought a notebook, a pencil and an eraser.
In the note book there are N points drawn in a row. The points are numbered from 1 to N serially.
Now, John decided to do a strange thing with those points.
At each moment, John puts his pencil or eraser at a point A and drags it to point B. As a result, some line segments may be created.
And then, Sometimes he stops and thinks of a point C and tries to find out if point C is on a line segment or not.
You have to solve a similar problem.
INPUT:
First line of the input will contain two integers N (1<=n<=10^{9}) and M (1<=M<=10^{5}) where N denotes number of points and M denotes number of queries.
Then M line follows. Each line contains a query.
Each query will be one of the following forms:
0 A B: which means an eraser has been dragged from point A to point B.
1 A B: which means a pencil has been dragged from point A to point B.
2 C: which means you are asked to answer the state of point C. There will be at least one query of this type.
(It is guaranteed that A<=B and 1<=A, B, C<=N)
OUTPUT:
For each query of the form “2 C”, print a single line.If point C is NOT on any line segment then print 1.
Otherwise, print the start and end point of the segment.
See sample input/ sample output and explanation for details.
Sample Input
Sample Output
25 14
2 10
1 20 25
1 9 13
2 12
2 7
1 11 21
2 15
0 17 20
0 22 25
2 21
2 5
1 1 8
2 12
2 4
1
9 13
1
9 25
21 21
1
9 16
1 8
Explanation:
In the 1^{st} query, there are no line segments. So point 10 is not on any segment.
After 2^{nd} query, there is 1 line segment: [20, 25].
After 3rd query, there are 2 line segments: [9, 13], [20, 25].
In the 4^{th }query, point 12 is on [9, 13] segment.
In the 5^{th} query, point 7 is not on any segment.
After 6^{th} query, there is 1 line segment [9, 25]. ([9, 13], [11, 21] and [20, 25] segments will merge into only 1 segment).
In the 7^{th} query, point 15 is on [9, 25] segment.
After 9^{th} query there are 2 segments: [9, 16] and [21, 21].
In the 10^{th} query, point 21 is on [21, 21] segment.
In the 11^{th} query, point 5 is not on any segment.
After 12^{th} query there are 3 segments: [1,8],[9, 16] and [21, 21].
In the 13^{th} query, point 13 is on [9, 16] segment.
In the 14^{th} query, point 4 is on [1, 8] segment.
hide comments
mamedov_1:
20160907 11:16:47
What will happen if we have queries like (1, 1, 10), (0, 5, 5), and (1, 5, 5)? Do we remain with line segments [1, 4], [5, 5], and [6, 10] or we will have only one segment [1, 10]? 

mahmud2690:
20160815 20:26:40
@Md. Najim Ahmed, can you check submission 17512434, i can't figure out why i'm getting WA. 

mehmetin:
20160106 12:37:52
@Najim: That's right, the overall complexity is O(N log N), although one query can go up to O(N) . Thanks, it's clear now. 

Md. Najim Ahmed:
20160106 11:31:48
@mehmetin: At first thought it would seem so.


mehmetin:
20160105 15:45:11
@Najim & @Yogendra: Are you sure this problem can be solved in O(log N) per query? I got accepted using set like data structure from Boost, and it seems like it goes to O(N) per query in the worst case, N being the total number of segments that must be merged in an update operation. Last edit: 20160105 15:59:43 

Yogendra Kumar:
20151228 23:18:44
Thanks Md. Najim Ahmed! got your hint a little late but I did it finally. Awesome feeling to be the first java solver.


Md. Najim Ahmed:
20151218 07:16:39
#Hint: Use Set like Data structure to reduce it to M*log2 (N) :) 

Yogendra Kumar:
20151215 23:25:45
@Md. Najim Ahmed, Thanks for the explanation.


Md. Najim Ahmed:
20151215 16:13:27
i don't see why there should be a confusion about that .


Yogendra Kumar:
20151215 12:54:50
What is expected from operations 0 A B and 1 A B when A == B ? 
Added by:  Md. Najim Ahmed 
Date:  20151210 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 