I was solving problem Chef and Sets in Codechef, but i could not solve it fully. I looked the editorial and found out that it was solvable through Treaps, a data structure i never heard of. I just wanted to ask what are the advanced data structures am i missing? It will be great help if anyone of you would list the important ds for the competitive contests. Here are some ds , i am aware of : 1.Array 2.List 3.Stack 4.Queue 5.Binary Tree 6.BST 7.Heap 8.Hash 9.Segment Tree( 1D only ) 10.Graphs
P.S It will be helpful if you could list the missing ds with their tutorial links or study material. P.S Positive responses are appreciated.
Trie, Sqrt-decomposition, DSU, Treap ... E-maxx
DSU ?
DSU stands for Disjoint Set Union.
DSU = Union Find
You can also solve it with available stl library in c++ and use of fast union-find method.Even many problem like this is solvable in just few lines of codes. Although i am not able to think this solution because of some time issue problem and my slow internet connection.And I get to know by some others solution.Here is the code if you like. Even this problem can also be solved by it. My solution is here. You can find tutorial on this special class stl on somewhere's blog on codeforces itself.
part1 part2