Hello, at problem E last contest I have do segment tree and binary search which reach a good complexity O((n+q)log(maxY)log(n)) but i dont know why It just give me a TLE judgement on test 18 Maybe my poor implementation ? Or there's some infinite loop ? Or I just make a wrong calculation in complexity ? I still cant find my mistake so I hope u guy could help me. Here is my code: https://codeforces.me/contest/1440/submission/98824111 Thanks in advance.
I think your type 2 queries might be $$$\mathcal O(\log^2 n \log y)$$$.
while (pos <= n): This while loop executes $$$\log y$$$ times, once for each continuous segment.first_small(pos,y),Get_pos(pos,y): Both of these seem to be $$$\log^2 n$$$ operations. They each have a $$$\log n$$$ while loop and callGet(1,1,n,pos,m)orGet(1,1,n,m,m)at each iteration, which is another $$$\log n$$$ operation.To remedy this, replace
Get(1,1,n,pos,m)orGet(1,1,n,m,m)by simply checking the sum of the subtrees in $$$\mathcal O(1)$$$ when deciding which children to traverse to.i got it,thank you so much for helping me. But i have use some technique called walk on tree. Is it what you mean ?
Yes, I was describing walking down the tree in my last sentence :)