| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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).
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.
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]).