An array of n elements is given. In this array, How many intervals [l,r] contain at least two 2 ? How many intervals [l,r] contain at least one 4? How many intervals contain two 2 and one 4 together? Note that, [1,1],[2,2] these intervals are also valid. Each of them contains 1 element.

Size of n is 1e5.

Hint: For the first problem, For each 2, count the number of intervals that contain it assuming that it is the rightmost 2 in that interval.

The same trick applies to the rest of the problems (with small variations).

But what about these — 2,2,2,4,4,2,2,4

How many intervals [l,r] contain at least two 2 ?

-> Store the indices for all '2' that appear in the array in increasing order.

-> Now iterate over this new array (lets call this new array B and original array as A). For each index of the new array B calculate the number of segments in the original array A which have A[B[cur_index]] as the leftmost 2. (This is simply (B[cur_index]-B[cur_index-1])*(B[cur_index+2]-B[cur_index+1]) if cur_index-1 and cur_index+2 are defined. You have to take care of end points)

Similarly go for other questions.

I have solved 1st two questions. But same approach is not working for 3rd one

The idea is similar.

B will now have indices of all 4s and 2s. Just think about it.

I have solved all the questions . And it was not this -(B[cur_index]-B[cur_index-1])*(B[cur_index+2]-B[cur_index+1]) .

Rather , it is this — (B[cur_index]-B[cur_index-1])*(n-B[cur_index+1]+1) I can't thank you :3 But thank you may be if you suggest me more similar problems :D

You can use binary search.Make an array,pre2[],pre4[],to denote the # of 2's and 4's before a index.For problem 1,find the largest index j for each i that pre2[j-1]+2<=pre2[i].Do it for the other tasks,as well.For problem 3,find max(pre2[j-1]+2<=pre2[i],pre4[j-1]+1<=pre4[i]).