@rishivikram Find the middle element of the sorted segment [l, r]. If there is a dominator this middle element has to be that dominator. Finding kth element could be done in (logn)^3 time in subarray with updates. Then count how many times this element appears in the array [l,r] This could be done in (logn)^2
@vsp4 Kth element in sorted segment can be found in O((logN)^2) by merge sort tree. I don’t know how to handle updates though, how do you find it in O((logN)^3) when updates are there as well?
This was my solution too.
Can anybody tell me how to define structure of segment treee such that i have an array of occurences of variable length in c.
Also plz tell me how to define map in c.
@rishivikram
For updates, erase the old element from each of the logn segments where the given index occurs and add the new element. It takes (logn)^2 time with a bst at each node of segment tree.
I also don’t know how to do updates with merge sort tree online. However i think a offline approach is possible by creating the tree with all possible values initially and erasing/inserting positions at old/new values respectively.
I tried with approach similar to merge sort tree: CodeChef: Practical coding for everyone But again got TLE with both operations on (log (n + q))^2. The order statistics bst seems to have very high constant!!!
It passes only if i distinct b/w heavy and light elements: CodeChef: Practical coding for everyone