We had this exact same problem on the list of candidate problems for the Romanian IOI selection contests, which usually take place in April-May each year, with the sqrt decomposition solution in mind. We’ll now have to erase it from that list. On one hand it’s a pity that we lost a nice problem that we could have used for the contests in Romania. On the other hand, I didn’t have to spend any time to think about the problem - I just implemented the solution that I already knew.
2 Likes
Please elaborate more on the relation between experiment_id and node.auxiliary in solution of tester link.
By now, I am thinking that the node.auxiliary field is represent for the primary without taking into account all edges from Query Q.left to right = MIN(Q.right, (L + 1) * MAX_SZ - 1);
Therefore, I made some trivial modification like these:
In function
int FindPrimaryAux(int a)
{
if(node[a].primary == a) return a;
node[a].experiment_id = nexperiment;
return node[a].primary = node[a].auxiliary = FindPrimary(node[a].primary);
}
I changed to
int FindPrimaryAux(int a)
{
node[a].experiment_id = nexperiment;
if(node[a].primary == a) return a;
return node[a].primary = node[a].auxiliary = FindPrimary(node[a].primary);
}
This change leads to Runtime Error
Or if I change to
int FindPrimaryAux(int a)
{
if(node[a].primary == a) return node[a].auxiliary = a;
node[a].experiment_id = nexperiment;
return node[a].primary = node[a].auxiliary = FindPrimary(node[a].primary);
}
It leads to Wrong Answer.
Could Manbubul Hasan give me the answer, please ?
Can you tell how do we restore the the union find at the end of merge operations ?
1 Like
adding using dsu is possible…but how to roll_back or remove an edge from it… ? can anyone please explain this?
Author here, I answered gojira’s question. I have to add, more presence on Stack Overflow’s [algorithm] tag could help fight this problem in the future, since this stuff happens all the time (questions about running contests being answered).
2 Likes
I think you will have to look more into research material (papers, lecture notes etc.) rather than “tutorials”. A good starting point would be Wikipedia, which also contains references to the original ST-Tree paper and some lecture notes. I can personally recommend the videos of Erik Demaine’s lectures about advanced data structures. Lecture 19 from 2012 is the one where he talks about dynamic trees. The one after that is about Euler-tour trees, amongst others
3 Likes
First understand bottom-up splay trees thoroughly, as they are the basis for the most practically efficient dynamic trees. Thing is, the big-O constant for dynamic trees is substantial – I submitted a solution using my extensively tuned dynamic tree library, and it was four times slower than my other solution that just used parent pointers. They’re still worthwhile in some cases though.
1 Like
@niklasb i read your answer bro. i know you havent done that intentionally. and i agree with you on growing stronger on SO as a CP community. anyway, if you wish, i can delete my answer here. my intention was not to give bad image to you @niklasb, im aware of your efforts to help to CP community and thanks for your help
You can leave the answer if you want, in fact it is good that people get directed to my response
2 Likes
ok bro, i hope i dont discourage you from helping us by posting good tutorials, answers, etc
Thanks a lot both of you.
You can assume there is a black box (link-cut tree), which supports finding the minimum edge on the path between two tree nodes and deleting/inserting an edge to a tree in O(logN) time.
After that, you can search some materials to learn the LCT, as niklasb mentioned.
@shangjingbo: thanks. I couldn’t understand because of not knowing LCT well . Now I have read it and therefore understood what your solution meant.
i got it!! in dsu whenever we are adding a node and if the parent of any node changes then we can store it in a vector and then redo those steps one by one from last(cost me a few WA) 
3 Likes
But how do you redo those steps?
could anyone provide an understanable code of sqrt decomposition , ive gone through the solutions above but unable to keep tract as this is new topic for me