Pile of Crabs

This problem can be solved using $Segment$ $Tree$.
First, take an array sized $N + Q$. Let’s populate the array with crabs according to their numbering. Only $N$ indices will be filled and the last $Q$ indexes will remain empty. For each event, we will take a crab, and place it after the last used index. And we will have to keep track of their health.

This whole process can be done using $Segment$ $Tree$ with $Lazy$ $Propagation$. Our Segment tree will have the following properties:

• Each node will save that if there any health decrease update for this range of crabs for lazy updates.

• Check the health of crab numbered $X$.

• Decrease the health of all crabs after the position of crab $X$ to the crab placed at the top of the pile. We will save the update of decrease as a lazy value for our desired range.

• Place crab $X$ after the current crab, that is on the top of the pile.