Hide

Problem C
Cheer Readers

The School Library Pep Squad is a squad of cheerleaders hoping to push the students in the library to study harder.

There are $N$ cheerleaders in the squad, labeled from $1$ to $N$ for simplicity. To improve their routine, they decide to hold $Q$ after-school events for the cheerleaders to meet with each other. When two cheerleaders who are not already friends participate in the same event, they become friends.

In the $i^\text {th}$ event, either:

  • the cheerleaders labeled $X_ i$ and $Y_ i$ participate, or

  • all the cheerleaders with labels from $X_ i$ to $Y_ i$, inclusive, participate.

A pair of cheerleaders $x$ and $y$ are considered compatible if $x$ and $y$ are friends, or there exists some cheerleader $z$ such that $x$ and $z$ are friends and $z$ and $y$ are compatible.

The number of pairs of compatible cheerleaders has a big effect on the quality of their routine. Please determine the number of pairs of cheerleaders who are compatible after each event.

Interaction

First, your program should read two integers $N$ ($2 \leq N \leq 10^9$) and $Q$ ($1 \leq Q \leq 200\, 000$), the number of cheerleaders in the squad and the number of after-school events, respectively.

Then, we repeat the following process $Q$ times:

  • Your program should read the event. Each event begins with a single integer.

    • If this integer is $1$, two integers $X_ i$ and $Y_ i$ ($1 \leq X_ i, Y_ i \leq N$; $X_ i \neq Y_ i$) follow, denoting that an event is held with the two cheerleaders labeled $X_ i$ and $Y_ i$ participating.

    • If this integer is $2$, two integers $X_ i$ and $Y_ i$ ($1 \leq X_ i < Y_ i \leq N$) follow, denoting that an event is held with the cheerleaders labeled from $X_ i$ to $Y_ i$, inclusive, participating.

  • Your program writes a single line to the standard output containing a single integer, the number of pairs of cheerleaders who are compatible.

Note in particular that your program will not be provided the next event until you have provided the response for the current situation.

After you have provided all $Q$ responses, your answer will be checked. Your program should terminate immediately after this.

After giving each response, do not forget to output end of line and flush the output. To do this, use:

  • fflush(stdout) or cout.flush() in C++;

  • System.out.flush() in Java;

  • stdout.flush() in Python;

  • see documentation for other languages.

Sample interaction

Your output (standard output)

Kattis’ answer (standard input)

Interpretation

 

$\texttt{6 3}$

There are $N = 6$ cheerleaders and $Q = 3$ events.

 

$\texttt{1 1 5}$

The first event involves the cheerleaders labeled $1$ and $5$. Thus cheerleaders $1$ and $5$ are friends.

$\texttt{1}$

 

Only the pair of cheerleaders $1$ and $5$ are compatible.

 

$\texttt{2 2 4}$

The second event involves the cheerleaders labeled $2$, $3$ and $4$. Thus cheerleaders $2$ and $3$, $2$ and $4$, and $3$ and $4$ are friends.

$\texttt{4}$

 

The pairs $1$ and $5$, $2$ and $3$, $2$ and $4$, and $3$ and $4$ are compatible.

 

$\texttt{1 1 6}$

The third event involves the cheerleaders labeled $1$ and $6$. Thus cheerleaders $1$ and $6$ are friends. Note that cheerleaders $5$ and $6$, though not friends, are compatible.

$\texttt{6}$

 

The pairs $1$ and $5$, $1$ and $6$, $2$ and $3$, $2$ and $4$, $3$ and $4$ and $5$ and $6$ are compatible.

Please log in to submit a solution to this problem

Log in