Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

practice_practice's blog

By practice_practice, history, 2 months ago, ,

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.

• +3

 » 2 months ago, # | ← Rev. 4 →   +8 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).
•  » » 2 months ago, # ^ |   0 But what about these — 2,2,2,4,4,2,2,4
 » 2 months ago, # | ← Rev. 2 →   0 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.
•  » » 2 months ago, # ^ |   0 I have solved 1st two questions. But same approach is not working for 3rd one
•  » » » 2 months ago, # ^ |   0 The idea is similar.B will now have indices of all 4s and 2s. Just think about it.
•  » » » » 2 months ago, # ^ |   0 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
 » 5 weeks ago, # | ← Rev. 2 →   0 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]).