# How to solve KRILLIN

### Moreover median can be found using segment tree for sum query… Having a leaf node containing frequency of each element…

#### You also need a sum of frequencies for Segment [1,l-1] which is again O(logn) for segtree…

Now u have sum of frequencies from starting to l-1th element…
As well as sum of frequencies in segment [l,r]
Now Hence you know where from starting your median will be there (do ask if u don’t know that)

### Hint :

Click to view

It will be there in middle of [l,r] so you will find it at (freq(1,l-1)+((freq(l,r)+1)/2))th number from starting…

### OR

median is average of ((freq(1,l-1)+(frequency (l,r)/2))th element + element after that
##(Yes , depending upon frequency%2)

Now you know that it is at (let’s say) kth element from starting… if we make a real list using frequencies but you can’t
make one due to bounds of space and time… So,

### Again a log(n) approach for getting kth element from starting using segtree tree (sum query tree) we made…

recursively check
 if k<= SumFreqency_LeftNode getElement(leftNode,k); else getElement(rightNode,k-SumFreqency_LeftNode)

Something of this type…
Thanks So basically 4 times O(log(n)) things to do for each query…

@l_returns for finding median can’t we just apply Binary Search for the Sum(0, L-1) and Sum(0, R). That is just looking for the first element in L, R whose sum is either greater than or equal to the required. The time complexity will be [log(N)]^2.

It may also be solved by using sqrt decomposition(Code will be shorter than segment tree)

Decompose the whole array of size N into \sqrt{N} blocks of size \sqrt{N}.

Now, preprocess the array to store i for which A[i] is maximum, and the sum of elements in that block, for each block which can be done in O(N) by just traversing the array once.

Query: For mode i.e index i for which A[i] is maximum, observe that any range [L,R] can be broken into few complete blocks (\leq\sqrt{N}) and two or less partial blocks. You know the value of sum and A[i]_{max} for complete blocks and for partial blocks you can just iterate and calculate. You will need at max 3$\sqrt{N}$ iterations. By using sum you can find median and i for A[i]_{max} is mode.

Update : just update the sum and i for A[i]_{max} just for the block in which i lies. Complexity O(\sqrt{N}).

Total Complexity for algorithm is O(N + Q\sqrt{N}).

Ps : I didn’t try this approach during contest but mentioning it as an alternative approach.

2 Likes

Okay okay… Got that… Ya we can I guess…

I am getting TLE. I don’t know why?

I have made two segment trees : one for finding the maximum and other for finding the sum and in that range.
I have used some binary search sort of thing to find the median.

Here is my code :

https://www.codechef.com/viewsolution/18897277

please someone help me in figuring out the bug