Editorial for DMOPC '21 Contest 7 P2 - Knitting Scarves

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: AQT

Hint

Doubly Linked List.

Full Solution

We will perform these queries on a Doubly Linked List to achieve a constant time.

Each node in this Linked List will represent a node with a certain value. Each node will have a pointer to the next node and a pointer to the previous node. Thus, initially the node that holds value $v$ will point to $v+1$ for the next pointer and $v-1$ for the previous pointer. Note that to make the implementation easier, we can have nodes with value $0$ and $N+1$ to represent the head and tail of the Linked List.

When performing a query, it helps to see for every relevant part of the Linked List how will their pointers change. For a particular query $k, l, r$ we also need to keep track of

1. $x$ , which is the next pointer of $k$
2. $a$ , which is the previous pointer of $l$
3. $b$ , which is the next pointer of $r$

The query makes

1. $l$ right after $k$
2. $x$ right after $r$
3. $b$ right after $a$

When setting $p$ right after $q$ the next pointer of $p$ points to $q$ and the previous pointer of $q$ points to $p$ . It helps to draw the before and after visually. Finally, after performing all the operations, starting from the head of the Linked List, we can iterate through the nodes by using the next pointer until we reach the end.

Be careful when implementing. In particular, first take out the array that starts with value $L$ and ends with value $R$ first and then insert them back into their new appropriate spots.

Comments

There are no comments at the moment.