Hello everyone, I tried recently this problem, but unfortunately I got TLE. I am using an O(nlogn) algorithm as supposed( a segment tree for updating the list and a map to keep track of frequency of each number and it's position ). I think there is some overhead with the update function -- can I rewrite it iteratively ? Any suggestion is welcomed.
Here is my code: link
Note: if someone can redirect me to a non recursive implementation of segment trees that will be great.
I solved it with the same (recursive) approach, but I did not use a map. I compressed the input values by using an auxiliary array (and by sorting it). It passes in 0.171 seconds and 3965 KB.
Can you please explain more. A tiny example will be perfect :)
For the sample input:
I keep a copy of the input, I sort the "copy" thus getting this:
I assign increasing numbers k to "mark" distinct values (in this case there are 2 distinct values):
(while computing this, I store for each i the corresponding k).
Then, for each i (from 0 to q - 1), I add/remove the number (which I get from the "original" input) in/from the k-th position.
Code here
Thanks dude! Good explanation and good solution too ;)
I've used the segment tree realization, which I know as "Implicit segment tree". The main idea is to build segment tree on whole range of numbers (from 1 to 1000000000 in this problem), but nodes we create only when they are need.
My solution passes in 0.187s with VC++ compiler and 0.343s with G++.
The link that you gave me doesn't work ( empty page ). I am the only one ?
You know what I got it accepted with VC++ compiler too. But, I am highly interested in your solution, please fix the problem.
My solution using an implicit segment tree. There are at most
100000
numbers to store; a root-to-leaf path requireslg(1000000000) ~ 31
nodes in the segment tree. Pre-allocate a pool of nodes of size100000 * 31
, whenever you want to create a new node, fetch it from the pool (faster than malloc-ing at runtime). Update is similar to ordinary segment tree (I use left/right pointers).