Fype's blog

By Fype, 16 months ago,

• +167

 » 16 months ago, # |   +27 any suggestion ? :DRemove "advance data structures" tag.Segment tree is way away from advance data structures.
•  » » 16 months ago, # ^ |   +8 Ok
•  » » 16 months ago, # ^ |   +3 Can you suggest some advance data structures which are useful in competitive programming.
•  » » » 16 months ago, # ^ |   -7 You can check this out. 6.851: Advanced Data Structures
 » 16 months ago, # |   0
•  » » 16 months ago, # ^ |   +8
•  » » » 16 months ago, # ^ | ← Rev. 2 →   0 added thanks
•  » » 16 months ago, # ^ |   0 All of these are already in list
 » 16 months ago, # | ← Rev. 3 →   +8 One more: 1172F - Nauuo and BugBTW, I think it would be better if you sort these problems by difficulties, or classify them into different types, like this blog.And do you choose all the problems which are solvable by segment tree, even if there are both faster and easier solutions? I've noticed that 516C - Drazil and Park only needs RMQ, and 516D - Drazil and Morning Exercise's official solution doesn't need any advanced data structures (I don't think union-find-set is), however, I have a solution using segment tree with worse complexity ($O(qn\log^2 n)$) but less observation, does this make it a segment tree problem? Or there are faster segment tree solutions?UPD: seems that these two problems are from this blog.
•  » » 16 months ago, # ^ | ← Rev. 4 →   0 Thanks, the problem added to the list.When you are unfamiliar with the segment tree it's better to solve the problem using the segment tree even if there is a better time-complexity because you will understand different usage of the segment tree. (At least that's what I believe)I never came across a faster solution for 516D.
 » 16 months ago, # |   -11 +
 » 16 months ago, # |   +5
 » 11 months ago, # |   -16 thank you. Its near to usless to me. Thank you.
 » 4 months ago, # |   0 Can anybody help me with the SPOJ-PERMPATT problem? I saw people building segment trees for finding minimum element but there should be one more idea i cannot catch.