Restructuring Company

Source: Codeforces 566D

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.

There are three operations in the problem. Two of them should look very familiar!

2. How would you do the problem if there were no queries of type 2?
   • What data structure operations correspond to type 1 and type 3 queries?
3. Implement this idea in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Write a program which solves the restricted problem.
   • Run your tests and debug if necessary.
4. Does this data structure also support queries of type 2?
   • Don’t worry about doing anything clever yet; we’ll get to that later.
   • What is the time complexity of this first attempt at handling type 2 queries?
   • Design a test case where this attempt is too slow.
5. A direct implementation of type 2 queries may perform a lot of unnecessary merges. Can we reduce this?
   • Can you keep track of some merges that definitely don’t have to be done?
   • Remember that once things are merged, they never get un-merged!
6. Can we answer each individual type 2 query in less than linear time?
   • If so, design an algorithm to do it.
   • If not, why not? Design a counterexample.
     • What’s the next best we can hope for?
     • Can you bound the total merges performed in all type 2 operations?
     • Design an algorithm to do this, extending your idea from the previous question.
7. Implement this algorithm in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Extend your earlier algorithm to solve the full problem.
   • Run your tests and debug if necessary.
8. Submit your program for judging!
   • Debug as required.