columns of numbers and union-find structure

Question

The problem:
Put the numbers from 1 to M into M columns. At the beginning column i contains only number i. Then, perform N queries of two possible types:

1. A i j: remove all numbers from column i and put them (in the same order) at the end of column j
2. B i j: if the numbers i and j are not in same column, print -1; otherwise, print the number of elements strictly between them.

The constrains are N <= 200,000 and M <= 30,000

My approach:
I though of using a union-find structure to solve the problem. The issue is that a union-find doesn't remember the order of the elements of the sets that it builds, therefore I would not be able to fully answer queries of type B.

Could you give the solution or at least some hints to guide in the right direction ?

Answer 1

You can use a union-find data structure if you keep track of the size of each root set (just use union-by-size instead of union-by-rank), and add an additional delta field to each node, such that:

• In set roots, delta gives the position the root element in the list of the set's elements; and
• In other nodes, delta gives the difference between the element's position and its parent's position.

This makes it easy to find the position of elements during "find" operations, which you can use to answer type (2) queries.

Type (1) queries would be implemented by union. The additional delta fields are easy to update in both set-union and path compression operations.