№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 150 |
Название |
---|
Yes, the problem is very difficult. At least at my level. Looking at bruteforce I can see that there needs to be some property that will reduce the runtime from $$$O(N^3)$$$ to at least $$$O(N ({\log N})^k)$$$.
When you think about the final array, you know some useful numbers. $$$\frac{N(N+1)}{2}$$$ is the number of elements in it. Similarly, when number
x
is a median of that array, there must be at least $$$\frac{1}{2} \cdot \frac{N(N+1)}{2}$$$ elements>=x
. For example, when there's only 1 unique number in that array, this property holds, when all numbers are unique, this property holds.So if you can somehow count the number of elements
>=x
in that array of subarray medians quickly (e.g. $$$O(N)$$$ or $$$O(N \log N)$$$) you can binary search for the moment when this count drops below $$$\frac{1}{2} \cdot \frac{N(N+1)}{2}$$$, all numbers greater than median will have less than half numbers greater than or equal to them.What you notice first is that you do not have that array with $$$\frac{N(N+1)}{2}$$$ elements. You only have $$$N$$$ elements, but, the condition for counting still holds. If you can count the number of subarrays where there were more than $$$\frac{L}{2}$$$ (
L
is length of subarray) elements>=x
, you also count all of the elements in that array of subarray medians that are>=x
. The way you count this is by +1 -1 mapping and count all subarrays where sum of that is>=0
. In that case you know that in each subarray there was $$$\geq\frac{L}{2}$$$ elements greater thanx
. When sum is 0, the element was the median as there was equal number of<x
and>=x
, when sum is>0
the element might have been median but it also might be less than median, if<0
thenx
is surely higher than median because more than half of array was smaller.Now, you have binary search on
x
and this counting subproblem. This counting subproblem with>=0
is somewhat related to a simpler problem of "counting all the sums in subarrays where sum is equal to K". This one we know how to do in linear time. The difference here is that>=K
is a bit more involved, because every time your prefix sum appears, you need to include not just the count ofprefixSum-K
but all previous sums whereprefixSum-K>=0
. You can do this with a BIT, counting all sums on the range-N
andp+1
(exclusive, wherep
is the current prefix sum). Or I assume they use "inversion number" for whatever they use to count this. I do not know what that is.Below is $$$O(N^3)$$$ that calculates this count for each element in
a
but you want to binary search it and get this sum efficiently.With BIT, this is a $$$O(N (\log N)^2)$$$ solution. There is a way to not use BIT and get $$$O(N \log N)$$$, this way exploits the fact that your prefix sum
p
only increases/decreases by 1. I'll skip that here.