| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
Всем доброго времени суток. Наткнулся на задачу, даётся n,m массив A длинны n(n<=100000), далее нам требуется отвечать на m(m<=100000) запросов вида l,r,x требуется на отрезке от l до r найти первое A[i]>=x(и вывести i). Если кто знает как решать прошу в комментарии описать свою идею.
UPD Огромное спасибо I_love_Tanya_Romanova и linjek за исчерпывающие ответы. Ну и конечно Neodym за шутку.
Прочтите о дереве Фенвика.
Извини за возможно глупый вопрос, но что это мне даст?
Предположу, что ALEXKIRNAS хотел сказать что-то такое:
Сожмем входные числа, отсортируем запросы по спаданию левого края, будем обрабатывать массив справа налево, в каком-то массиве Х будем для каждого числа из входных данных хранить самое левое из его вхождений, которое мы уже встретили (или INF, если такого числа еще не было), и после добавления числа на позиции t считать ответы на все запросы, в которых l=t. Тогда ответ на запрос l r x — это минимум из значений Х[i] по всем i>=x, или -1/No solution, если этот минимум больше r. Для нахождения минимума на суффиксе массива можно использовать дерево Фенвика.
Но здесь слишком много букв, он написал немного короче:)
Лучше Бинарным поиском.
Эмм... не получится бинарным поиском. Бинарный поиск применим только к монотонным функциям. А в условии не сказано что массив отсортирован. Тут скорее дерево отрезков.
Как раз таки можно. На каждый запрос делаем бинарный поиск от l до r. Пускай у на есть middle. Проверяем, что максимум на отрезке [l, middle] >= x. для нахождения максимума на отрезке можно использовать sparse table.
Что-то я не понял. Проверили, и что? Если максимум больше x, то надо идти вглубь этого отрезка, так? А если и max([middle+1, r])>x, то мы и вправо должны пойти. И где тут будет меньше O(n)? Например массив состоит только из чисел 2, а во всех запросах x=1.
Внутри бинарного поиска проверяем, есть ли на отрезке число, которое не меньше х (это делаем за О(1) с помощью sparse table). Нам нужно с помощью бинарного поиска найти наименьшую длину, для которой это выполняется — понятно, что на отрезке этой длины искомым является последний элемент, потому что на более коротком отрезке без одного последнего элемента наше условие уже не выполняется.
Ну можно написать за O(m*log(n)*log(n)) — с помощью бинпоиска от l до r и дерева отрезков.
Если возможно опишите поподробнее решение.
Будем считать что числа содержатся от 1 до n в массиве. Строим дерево отрезков на изначальном массиве. (В вершине будем хранить номер вершины j, a[j] — которое максимальное, если у обоих сыновей значения равны, то берем минимум.), пусть это функция f, зависящая от 5 параметров. int f ( int v, int tl, int tr, int l, int r) Переходим к запросам , для каждого из них: r1=r; l1=l; While (r1-l1>0) { int mid = (l1+r1)/2; if ( a[f(1, 1, n, l, mid)]>=x) r1=mid; else l1=mid+1; } в f(1, 1, 1, n, l, l1) искомый ответ. Сорри что все слитно, до сих пор не понимаю как тут перенос делать.
Раз уж подняли тему.
Перенос делается двумя переводами строки.
Или кстати можно те же sparce table написать, предподсчет тогда за nlogn , и потом тем же бин поиском находить ответ, тогда получится в итоге. ( (n+m)logn).
А потом избавиться от одного логарифма, находя ответ сразу при спуске по дереву. А потом обойтись деревом фенвика, заметив, что r в запросе ни к чему.
Прочитал название блога как "Не отказался бы от Польши". Не знал уже, что и советовать.
Ненавижу CF. Всякие смищные баяны почему-то собирают плюсы
К сожалению, таков уровень интеллектуального развития большинства местных пользователей.
Мне, кстати, не очень нравится негласное правило "видишь любую дискуссию — плюсуй того, у кого больше рейтинг", но вас минусуют даже за адекватные комменты. Традиция наверно:)
Я зашёл в эту ветвь когда был только комментарий "Ненавижу CF. Всякие смищные баяны почему-то собирают плюсы" и я поставил ему решительный минус, ибо это комментарий под своим же сообщением. Непонятно зачем человек воскресил пост месячной давности, возможно кармодрочерства ради. И да, поскольку у этого комментария +10, то как минимум 11 "интеллектуалов" здесь присутсвуют.
Кармадрочерство? Вы чего? :)))
Не надо иметь образование психолога, чтобы понять — если кто-то называет других тупыми идиотами, то у части из них может сформироваться субъективное негативное отношение к данному человеку и всем его высказываниям:)
прочитай это
Можно ссылку на задачу? Не понимаю почему нельзя решать проходом по массиву слева направо, поддерживая set из активных запросов, упорядоченный по x, тогда будет m*lg(m)(отсортировать запросы и расставить метки) + n (пройтись) + m*lg(m) (обработать). Хочу проверить.
Задача с Беларуской республиканской(ссылку потерял).