Hi everyone,I have been trying this question SPOJ K-QUERYfor 2 days now.After unsuccessful attempts to come up with logic,I finally referred Blogs available online.But I am neither getting head nor tail of the logic. Can someone please tell me the formation of fenwick/segment tree that is used(especially the technique used).It will be a great help.Please! Thanks in advance.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 160 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | Dominater069 | 154 |
| 8 | awoo | 154 |
| 10 | luogu_official | 151 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 08:22:00 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
try amd blog on segment tree he has explained it nicely segment tree. If you still need help then ask.
That has been explained so many times... Just google it.
I had tried it.But I did not get good explanation .All the blogs gave code .I tried understanding it using pen and paper literally.But I could not get the basic strategy behind it.The best blog I got was of PrinceOfPersia , But still could not understand it. Instead of showing me How to Google ,It would have been great that you could have explained it to me. Anyways Thanks radoslav11....
Well the main idea is to solve the problem offline. At every query we should care just for elements with value < K. Lets make events. Every event will be either an adding of element at position POS with value VAL or a query.
We sort these events by VAL and K (depends if event is an adding or a query). Then our problem becomes:
For every query what is the number of added elements before it in range [L; R].
This can be done with an range-query and point update on segment tree or with a BIT: For every adding we set the value of POS with 1 and for every query we get sum of [L; R].
The complexity is O(Nlog(N) + (M+N)*log(N)) = O(Nlog(N)).
PS: The problem can be also solved online with a merge sort tree in O(N*log^2(N)) time.
Thanks radoslav11 and SORRY if you found my above comment offensive .I actually had tried lot before asking on the forum.Again Sorry!!