Hi guys, I have this problem. In a given array a length n, how many subarray are there that satisfies: max_element — min_element of the subarray is even. Given that 1 <= n <= 1e5, 1 <= ai <= 1e9. I can't figure out a better solution than O(n^2) solution. How to solve this problem? Thanks!
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 7 | SecondThread | 150 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 18.04.2024 12:37:54 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
What do you mean by consecutive subsequence? Contiguous subsequence(Subarray) or a subsequence which consists of consecutive numbers?
Contiguous subsequence. A subsequence that can be achieved by erasing a number of elements.
The task is to find the number of subarray that in each subarray, the difference between the max_element and the min_element is even.
It can be solved using prefix sums.
I don't think it's possible to solve using prefix sums, because the min and max functions aren't reversible.
The easiest solution I have in mind right now is a divide and conquer + segment tree solution (that runs in $$$O(n*log^2(n))$$$), I can describe that in a separate comment if you want.
Ah, my mistake, I badly misread the problem. Sorry for being misleading.
Here is the $$$O(n*log^2(n))$$$ solution I mentioned in a previous comment.
First, apply standard D&C (divide and conquer). Now our solution is reduced to find the number of segments that go through a specific index whose max and min have the same parity, in subquadratic time. I describe a solution that does this in $$$O(n*log(n))$$$
As you do in standard D&C, split each segment into two parts (the left half, and the right half, each on one side of the midpoint)
There are $$$O(n)$$$ segments on each side, so it is okay to iterate through all of them naively. First, calculate all of the min's and max's for all segments ending at the midpoint. Store them in two arrays, I'll call them $$$l$$$ and $$$r$$$.
Note: These are two arrays of pairs. In each pair, one element is the min, the other is the max of the segment it represents.
Now I just need to find the number of ways to pair an element form $$$l$$$ with an element from $$$r$$$ s.t. the min of the min's and the max of the max's have the same parity.
First sort the elements of both $$$l$$$ and $$$r$$$ by their max's.
WLOG asume the max of the max's is in $$$l$$$ (you can do a similar thing for $$$r$$$). Iterate through all of the elements in $$$l$$$. Store a pointer over $$$r$$$, and add the elements with a smaller max then the current element that we're considering in $$$l$$$ to a data structure. The number of r's that work for the current element that we're considering in $$$l$$$ is the number of elements in our data structure s.t. either:
What is that data structure? Here are the two queries we want to support.
To handle this, we can have two segment trees (or BIT's or ordered sets). In one, we store only even elements, and in the other we store only odd elements. Then, the problem is reduced to standard ops on the data structures.
Using Case 2 of the master theorem, you can see that the complexity of this approach is $$$O(n*log^2(n))$$$.
Let me know if this is confusing.
Can you explain the l and r array more clearly? Especially the part "calculate all of the min's and max's for all segments ending at the midpoint".
As in standard D&C, the goal here is to calculate the answer for all segments that pass through the midpoint. To do this, you look at each segment $$$[l...r]$$$ as a combination of $$$[l...mid]$$$ and $$$[mid+1...r]$$$. Because in this problem you only care about the min's and the max's of segments, that's all you need to store when considering the combination of two segments. In this case, the $$$l$$$ array stores both the min's and the max's of each segment whose right endpoint is the mid, and the $$$r$$$ array does the same except for segments whose left endpoint is the mid.
This idea is quite interesting , Like using two pointer we can iterate over the satisfied ranges and just checking for number < min of curr with parity = max of element AND for > min of curr just thier cnts if(parity of min = parity of max)
Can we have a better solution than this??
Fakesolved :(