I want to count for every number ,say A[i] ,how many numbers there are that is smaller than Ai with id smaller than i. For example , here is an array: 5 3 7 2 9 6 ,the anwser is 0 0 2 0 4 3 Is there any fast algorithm that can solve this problem? Thank you for your help!
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 8 | SecondThread | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 01.05.2024 20:32:34 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
Use Fenwick Tree, add 1 to tree[A[i] and ask for sum on tree[0...A[i] - 1]
If constraints are too big (A[i] <= 10^9) you can use segment tree with zipping vertexes; It means you will create vertex only when you will need it;
the problem can be solved with O(nlogn) complexity using segment tree:
Consider the array b[] where b[i] denotes the number of elements of A that are <=i
Traverse the array A[] from left to right, editing the array b[] on your way by adding 1 on the interval from A[i] to Max number in A[]. The answer for ith number is b[A[i]-1]
please correct me if I am wrong.
And changing limit for A[i] does not make much difference for this solution. You just have to compress all input numbers — say that smallest of them is equal to 1, second smallest is equal to 2 and so an. There will be no more than N different values in array of size N, so you'll end up with array of numbers <=N, even if original numbers were up to 1e18.
You are right, fixed, thanks.
Can this sequence "canonicalization" be done faster than sorting and then assigning? I've always used this method when I needed to, and I'm almost sure there is no better method (mainly because you need to know ordinal position for every number), but now I'm thinking about this.
By "sorting" I include any variant which implies the use of a set/heap or similar things.
edit: Sometimes I fail to understand why posts get downvoted :|
If you're able to get the position of each element in O(f(n)), then you can sort array in O(f(n) + n), but that's impossible if you use only comparison and f(n) ~< nlogn
What you're asking is similar to counting the number of inversions, though the comparison is the other way around. It can be solved with BIT / Segment Tree, like others have said, and also with a modified Merge Sort algorithm.
If i didnt get the question wrong it can be solved with a monotonic queue with O(n) time complexity.
EDT: Yes i did get it wrong. Sorry.
The problem can be solved without compressing the numbers.
Put Fi = 0 for all i < = N
Sort the pairs Pi = (Ai, i).
Then go from left to right, calculate the answer for Pi.second, which is (F1 + ... + FPi.second - 1). Do this with segment tree.
Then put FPi.second = 1
If there are repeated numbers in the array and you do it that way, you'd need to process the numbers in groups.
Pi = (Ai, - i)