I feel the explanation for dominant sub-arrays in the editorial is insufficient since it deals with only sub-arrays of size N/2. This is not always the case - especially in case of queries where the query range can span multiple segments(sub-arrays). I think this would be better way to put it,
Over a range(i,j) of length N, let there be k sub-arrays {1,2,3ā¦,k} each of length {n1,n2,ā¦nk} respectively. If a majority element āeā exists in range(i,j) then one of the k sub-arrays must have e as the majority element.
Proof is by contradiction (along the same lines as in the editorial),
n1 + n2 + ā¦ + nk = N
Assume e exists which means freq(e) in (i,j) > N/2
Now lets say none of the k sub-arrays have e as the majority element. Then,
freq(e) in sub-array {1] <= n1/2
freq(e) in sub-array {2} <= n2/2
ā¦
freq(e) in sub-array{k} <= nk/2
Therefore, freq(e) in (i,j) <= n1/2 + n2/2 + ā¦ + nk/2 <= N/2 which contradicts our assumption that e is a majority element.
So at least one of the k sub-arrays must have e as the majority element.
Could anyone tell me where I could be going wrong in this solution?
It is very similar to the editorial and though the running time is O(Q * (log N)^3), I am getting a WA verdict and not TLE. So could anyone tell me if thereās something wrong with the logic?
Can someone please explain the meaning of the phrase āelegant lazy propagationā in the line āClearly, There isnāt a notion of an elegant lazy propagation here since the updates we perform are to single elementsā
How can a segment be dominating if either of subarrays are dominating?? Consider a case [1,2,3,4][2,2,2,5],here 2nd subarray is dominating but when we merge them , the resulting array is not dominating!!
Initially we have 10^5 elements. Even if you consider the 10^5 query operations as āappendā operation instead of replace, at the end you would have 2 * 10^5 elements => at most 200 with >= 1000 frequency
@vsp4, I think your solution gives tle because of the ordered statistic set used in your solution. Though, the complexity of ordered statistic set is as desired, but constants are too large. It happened with me too when orderedd statistic set gave tle, but bit with binary search passed easily.
@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?
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!!!
