### LashaBukhnikashvili's blog

By LashaBukhnikashvili, 6 years ago,

I know you are tired coz of kquery's problems.I am just interested to solve this problem.without update I had on each vertex of segment tree sorted subarray,but now I can't do this with same idea (it was O(n log^2)). also is any idea which solves this problem in O(n log n) ?

• +12

 » 6 years ago, # |   +13 Disclaimer: There's a good chance this won't quite run in time.Divide the array into m equal-sized blocks. For each block, keep a binary indexed tree of the elements in that block. Then, for a query, you can make a single query to the BIT (to count elements less than k) for each complete block in the range, and for the two partial blocks on the end, just loop through the elements. Therefore, the query time is O(m * log(10000) + n/m). The update is just updating a single BIT = O(log(10000))Let m = 50. Then, the total time for 200,000 queries is 200,000 * (50 * log(10000)) + 600), which is about 250 million operations.I'm hoping there's a way to speed up the queries by slowing down the updates somehow but I can't think of any ways to do that right now.
•  » » 6 years ago, # ^ |   +5 This is a really beautiful solution!At first, I submitted and got TLE, but after playing with the block size, I got accepted. Here's my implementation of your great solution: C++ Code
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -8 Thanks mkirsche,nice idea to do same problems as this is,I got it ;)
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 Can't we use the same idea in segment tree? Each node will contain a BIT, which we can use to count elements less than k. Update is similar too.The solution is though (but it should be fast enough I guess).
•  » » » 6 years ago, # ^ |   0 your idea is different,in his idea he divides array into m equal-sized blocks,and you have structore for each node of segment tree.actually,it is also possible to Build BIT, Fenwick Tree , Treap for each node in segment tree(here we can also possible to swap Treap and Segment Tree,and on each node of Treap Build this structures) complexity for each case is O(n log^2 n).
•  » » » » 6 years ago, # ^ |   0 as Diguised say about 2D segment tree ,it's same as Build another segment tree on each node of segment tree and works also in log^2.
 » 6 years ago, # |   0 With updates you can do it in O(n log^2) if you replace sorted arrays with treaps. It is a bit complicated solution, may be it is possible to use something easier.
•  » » 6 years ago, # ^ |   +8 segment tree+treap it's so hard to implement,it's better to use mkirsche's solution in this way.
•  » » » 6 years ago, # ^ |   0 why segmenttree+treap harder than sqrtdecomposition+treap??? i thought it is the same...
•  » » » » 6 years ago, # ^ |   0 for me sqrtdecomposition is much more easier than treap to implement.
•  » » » » » 6 years ago, # ^ |   0 Oh, sorry, i misread solution in first comment. But now i don't understand why needed BIT if there can be just array.
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Okay then Had you been able to done this one by segment tree .I am now trying but it is getting TLE. I have used pbds with segment tree.If some how simple multi set can be used to do in query part then ...I think this would get AC. my code: https://ideone.com/T6hU4Q
 » 6 years ago, # | ← Rev. 4 →   0 Don't mind, it leads again to log^2.
•  » » 6 years ago, # ^ |   +8 Can you explain how you do the update with changing only one version?! Don't you need to update all versions with index >= j (If you're updating a[j])?
 » 6 years ago, # |   0 Use 2D segment tree or store a persistent segment tree at each node :D.
 » 6 years ago, # | ← Rev. 2 →   +8 The first time I AC this problem, I used 2D BIT, which cost so much memory (but it got AC). The main idea of this one is calculating S(x,y) which is number of elements lesser/greater than y in a[1], a[2], ... , a[x].Later I changed to BIT and sqrt decomposition with the same idea above. You know that a 2D BIT is N 1D BITs in someway. Instead of using N 1D BITs (which is actually a 2D BIT) for N element, I used sqrt(N) 1D BITs which would be a 2D [sqrt(N) x N] BIT. That's all, the remains are just basic sqrt decomposition technique.Complexity :O(2*log(sqrt(N)) * log(N) + 2*sqrt(N)) = O(sqrt(N)) per query.O(log(sqrt(N)) * log(N)) = O((log n)^2) per update operation....which is fast enough.I have no idea how to solve this in O(log n) per operation/query.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 your idea is good and different,but let n=2^xsqrt(n)=2^(x/2)log^2 (n)=x^22^(x/2)=x^2x=16,n=2^16=65536;if n>65536 as here and in more cases it's better to write log^2(n) solution,else your solution is much faster,It help's me thanks for your explanation.
•  » » » 6 years ago, # ^ |   0 please some1 tell me how to write formulas here same us in latex?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Disregard
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   0 (dollar sign)2^\frac{x}{2}(dollar sign) 
•  » » » » » 6 years ago, # ^ | ← Rev. 4 →   0 thanks ;)
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +5
 » 6 years ago, # |   0 Hi -recently I submit this code to this problem; except I get TLE. Solution utilizes 2D segment tree. Anyone can suggest any optimizations that will help it pass?Thanks in advanced-Disguised
•  » » 5 years ago, # ^ |   0 Hi, I used a range tree of treaps and it got TLE. Code: http://codepad.org/Zy7elORD It seems that the constant factor of a treap is pretty high >_<
 » 3 years ago, # | ← Rev. 2 →   0 Has anyone been able to get AC in this problem by storing an implicit segment tree in every node of a normal segment tree? I am getting TLE using this idea.Also how do you solve this problem by 2D segment tree or 2D BIT or by storing a BIT in each node of segment tree? Isn't that going to take too much memory?N.B.: I have solved this problem using square root decomposition plus BIT. Theoretically the complexity of the query operation for the implicit segment tree idea should be better while that of the update operation of the sqrt idea should be better. But I am interested to know if this problem can be solved using implicit segment trees within time limit.
•  » » 6 weeks ago, # ^ |   0 I got AC with it
•  » » » 6 weeks ago, # ^ |   0 Can you share the code?
•  » » » » 6 weeks ago, # ^ |   0
 » 2 years ago, # |   0 I tried segment tree with order statistics trees at the nodes got TLE :(
 » 2 years ago, # | ← Rev. 2 →   0 Thanks very much.
 » 6 weeks ago, # |   0 My O(N lg^2 N) code passes in 1.38s even though the time limit is 1sec lol. My solution: Coordinate Compression + BIT in Segment Tree.