**Suppose you are given an Array : a[] = { 0 , 0 , 1 , 0 , 0} . size of array can be large upto 2e5.** **** **You have to count all the subarrays in which a particular element x occurs more than length(subarray) /2 times**

for example if x = 0 :

subarrays are :

{0} index = 1

{0} index = 2

{0} index = 4

{0} index = 5

{0,0} index 1 --> 3

{0,0} index 4 -->5

{0,0,1}

{0,1,0}

{1,0,0}

{0,0,1,0}

{0,1,0,0}

{0,0,1,0,0}

ans = 12.

Any idea !

Could you explain more clearly? I don't understand. 'the subarrays in which a particular element x occurs more than length(subarray) times' — the length of the subarray is a maximum number of occurrences of a particular element x. It can't occur more times than the length of the subarray.

oops.. really sorry .. in a rush i did mistake.

its len/2.

see if u could help

I think I've got it in O(n log n) so it is enough for n <= 2e5. Create prefix array in such a way that prefix[i] denotes (number of x's in prefix i — other numbers in prefix i). For exemplary array it will be 1 2 1 2 3. You create it as below:

This is obviously O(n). Now let's go from the end of the array and for each i, count all the subarrays which start from i+1 and are proper.

`for(int i = n-1; i >= 0; i--)`

We can do it in O(log n). Number of subarrays that should be counted is equal to the number of such m: i < m <= n && prefix[m] — prefix[i] > 0. (it means that the prefix 'grows' so there are more x's than other numbers in the subarray). The results will be as below:How to know how many m's meet this condition for each i? We can keep them in tree. Leaves are all possible values of prefix[m] so there are n+1 of them. Every time we pass the prefix, we add it to the tree in O(log n). It guarantees that i < m <= n. When we want to count m's which meet the second condition, we can do it in O(log n), too. It's just a range query.

thanks , get the idea ! we can do a range sum on segment tree .

What are the constraints over the elements of the array ?

Is x known beforehand or we need to search for all x that satisfy this property ?

x already known to you