|
|
back to boardHelp me How can I solve this problem by using segment tree?? Re: Help me It was uneasy, but I did it! 3 days of thinking left. I use array of ranges. Each range is both-direction (parent-child) tree. I crossed the input 3 times (for read data, for evaluate a length of each subnode, for build array of ranges. I had such problems, such as TLE (I solved it with refusing of lists, I use child array[10^5] for each node). I get MLE-Memory limit exception (It solved with evaluate of node length O(n). it was hard!). The tree was a genious idea! But I had TLE, becouse I ran from 0 to ChildArr.Length everytime. I need in dynamically an BeginChildId for each parent. TLE went away from my eyes! 4 cycle has Mx(crossing the ranges) complexity. I used a PrevOtr object. 1 query could to have 1 or 2 ranges (begin of 2 range, so keep in mind! You must understand that). That is part of FindNode function code: ... do { prv = null; for (int i = inner.BegChild; i < inner.ChildN//inner.Childs.Count() ; i++) if (query >= inner.Childs[i].X && query <= inner.Childs[i].Y) { prv = inner.Childs[i]; inner.BegChild = i; break; } if (prv != null) inner = prv; } while (prv != null); ... Edited by author 15.10.2018 17:15 |
|
|