Augmented DSU
Suppose you have to maintain a consistent system of equations of the form xi−xj=d. Write an operation add(i,j,d) that decides if the equation xi−xj=d is consistent with the system and if yes adds it to the system. Complexity should be almost constant time per request.
A solution to this general problem consists in maintaining sets of variables that are connected by equations in the system. This is done with a classical union-find structure, where every component is organized in form of a tree. The root is the leader of the component. A precedence table prec indicates for every variable xi the predecessor variable xj in the tree with j=prec[i]. For the leader xi of a component we have prec[i]=i.
We augment this structure by assigning to every variable xi, a potential pot[i] with the idea that if j=prec[i] then xi−xj=pot[i]. By definition leaders of a component have zero potential. The potential between a variable and the leader of its component is by definition the sum of the potentials along the path from the variable to its leader. We have to update the potential accordingly when flattening the paths during a call to the find request.
Now on the operation add(i,j,d) we have to first verify if the variables xi and xj belong to the same component. In this case we can compare their potential and verify whether it satisfies the equality xi−xj=d, in other words verify whether the request is consistent. In case the variables belong to different components, these components have to be merged by making the leader of one component, say xk, a descent of the leader of the other component. There is a unique way to assign potential pot[k] that would be consistent with the given request.
The following code implements this data-structure. To obtain the right complexity, a correct implementation should maintain a rank for each component and merge only the smaller rank component into the large rank component. However in practice this implementation is good enough, even though in the worst case each request could cost O(log n) time.
Now let’s see the spoj problem http://www.spoj.com/problems/CHAIN/
This problem can be easily solved using this technique. Problem asks for the number of inconsistencies achieved in total.Realise that for query of type 1, you are basically asked to add the system of equation a-b=0 (mod 3) and for query of type 2, equation to be maintained is a-b=1(mod 3).And there is an extra inconsitency to be added as described in question is when either a or b is greater than n.Below is the AC code which implements this.
Cheers!! Happy Coding
