Hide

Problem A
Kanna's Friendship

Kanna is new to the human world and has recently made new friends due to her kind and personable nature. Possessing a sharp mind and an insatiable curiousity towards learning about the human world, Kanna is always keen to try new things. One day, while playing with her best friend, Riko Saikawa, Kanna found some LEGO™ train tracks. Being unfamiliar with how to join them together, Kanna places overlapping train tracks on top of one another.

After getting even more confused, Kanna consults Saikawa on whether she is attaching the pieces correctly. Saikawa suddenly realised that there could be a really good problem to solve! The problem is as follows: Saikawa can model an empty straight line with bullet points from $1$ to $N$ inclusive from left to right. Next, there will be $Q$ queries. Each query will be of the following $2$ types:

  1. Place a LEGO™ track to cover all bullet points from $s_{i}$ to $e_{i}$ inclusive.

  2. Query the total number of bullet points on the line which is covered by at least one LEGO™ track.

Input

The first line contains two integers, $N (1 \leq N \leq 2\, 000\, 000\, 000)$ and $Q (1 \leq Q \leq 200\, 000)$. The next $Q$ lines contain the queries each on one line. Each query starts of with $t_{i}$ ($1 \leq t_{i} \leq 2$), denoting the type of the $i^{th}$ query. If $t_{i} = 1$, then two additional integers follow: $s_{i}$ and $e_{i}~ (1 \leq s_{i} \leq e_{i} \leq N)$, the starting and ending covered bullet points of the LEGO™ track respectively.

Output

For all $t_{i} = 2$ queries, output the total number of bullet points on the line which is covered by at least one LEGO™ track.

Subtasks

  1. ($24$ Points): $N \leq 2\, 000$ and $Q \leq 2\, 000$.

  2. ($13$ Points): $N \leq 200\, 000$ and $s_{i} = e_{i}$ for all type $1$ queries.

  3. ($7$ Points): $s_{i} = e_{i}$ for all type $1$ queries.

  4. ($17$ Points): $Q \leq 2\, 000$.

  5. ($21$ Points): $N \leq 200\, 000$.

  6. ($18$ Points): No additional constraint.

Sample Input 1 Sample Output 1
10 12
1 5 5
2
1 6 6
2
1 5 6
2
1 2 4
2
1 3 8
2
1 1 10
2
1
2
2
5
7
10
Sample Input 2 Sample Output 2
26 19
1 8 8
1 15 15
1 20 20
1 19 19
1 16 16
1 21 21
1 18 18
2
1 1 1
1 9 9
1 9 9
1 7 7
2
1 1 1
1 20 20
1 8 8
1 9 9
1 14 14
2
7
10
11

Please log in to submit a solution to this problem

Log in