Hello there
I'm trying to solve this problem
So i was thinking if i create a segment tree where each node has a segment tree that would do the trick
I've heard about 2D segment tree before but never implemented it
the only way i could think off would definitely get me MLE where i do an array seg[n*2][n*2]
if anybody has any tricks that could save memory or maybe the correct way for creatin a 2D segment tree that would be really appreciated :D
You can build segment tree, where in each node you have a treap. It will be O(n * logn) memory.
Got any resources i can read from about treaps ?
kind of a new concept to me
link from Wikipedia
I've written a range tree of treaps for this problem. Unfortunately it timed out on spoj Here's the code http://codepad.org/Zy7elORD
your code will be very helpful to me in learning treaps thank you!!
i tried implementing and AVL tree in every node of a range tree but it timed out also ... i feel your pain
If you find treaps hard to understand, try more easy approach: Balanced Binary search Trees (AVL, Red Black)
This class of data structures are fit requirements in this problem (treap is also kind of balanced BST, but more complex and powerful). So they can do insert\delete queries in log time, as well as count (number of elements >= KEY).
You can think in the way that in every node of segment tree you have a set, that can answer the second query.
I understand that and i tried implementing an AVL tree in every node of a segment tree but unfortunately it TLEd
if you have solved this problem and it's too much trouble here's my code ... what am i doing thats too slow ?
This and This
thank you they were very helpful
Also you can use sqrt-decomposition with Fenwick tree. All what you need is to divide the array into parts of
and for every part maintains amount of every number (in fenwick tree). Then every modify query will be processed in O(log(N)), k-query in 
.
i've heard of sqrt decomposition but never tried it
guess now is a good chance while trying to implement your solution
If you still want to use 2-D segment tree, you can store in every node Dynamic segment tree.
The key idea is that you don't have to keep all the nodes of segment tree (which is stored in node I mean). You can dynamically create it as soon as you need it.
That is require O(n * log(n) * log(M))
Little example: '[1-4]=0 [1-2] [1] [2] [3-4] [3] [4] ' here is segment tree for 4 nodes. '=0' — indicates the vertex that was created already, and stored the value 0. So if vertex wasn't created means that there is no value in it ==> 0 there. let's make update query: add to +1 to 4-th, then the tree are gonna look like the following:
Let's provide query how much elements >= 2 in our Data structure. In our case is simply sum over segment [2..4]
Hope it make sense.
it makes so much sense :D
that was exactly what i needed thank you !!!