Need help with a data structure problem

Revision en3, by Roundgod, 2019-03-26 09:47:38

I found this problem on the problemset of a contest in some training camp, but counldn't find more information beyond that. The problem statement is as follows:

Consider n different urns and $$$n$$$ different balls. Initially, there is one ball in each urn.

There is a special device designed to move the balls. Using this device is simple. First, you choose some range of consecutive urns. The device then lifts all the balls form these urns. After that, you specify the destination which is another range of urns having the same length. The device then moves the lifted balls and places them in the destination urns. Each urn can contain any number of balls.

Given a sequence of movements for this device, find where will each of the balls be placed after all these movements.

First line contains two integers $$$n$$$ and $$$m$$$, the number of urns and the number of movements $$$(1 \leq n \leq 100 000,1 \leq m \leq 50 000)$$$.

Each of the next $$$m$$$ lines contain three integers count $$$i , from_i$$$ and $$$to_i$$$ which mean that the device simultaneously moves all balls from urn $$$from_i$$$ to urn $$$to_i$$$ , all balls from $$$from_{i + 1}$$$ to urn $$$to_{i + 1}$$$, . . ., all balls from urn $$$from_i + count_i − 1$$$ to urn $$$to_i + count_i − 1 (1 \leq count_i , from_i , to_i \leq n, \max(from_i , to_i ) + count_i \leq n + 1)$$$.

Could anyone please give a hint? Thanks in advance!


  Rev. Lang. By When Δ Comment
en3 English Roundgod 2019-03-26 09:47:38 1
en2 English Roundgod 2019-03-26 06:09:25 83 Tiny change: ' integers n and m, the numb' -> ' integers $n$ and $m$, the numb' (published)
en1 English Roundgod 2019-03-26 06:06:58 1366 Initial revision (saved to drafts)